BZOJ 2759 一个动态树好题 Link-Cut-Tree+扩展欧几里得

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 30300
#define p 10007
using namespace std;
struct line{
	int k,b;
	line operator + (const line &y) const
	{
		line re;
		re.k=k*y.k%p;
		re.b=(b*y.k+y.b)%p;
		return re;
	}
	int F(int x)
	{
		return (k*x+b)%p;
	}
};
struct abcd{
	abcd *ls,*rs,*fa,*sfa;
	line num,sum;
	abcd(int k,int b);
	void Push_Up();
}*null=new abcd(1,0),*tree[M];
abcd :: abcd(int k,int b)
{
	ls=rs=fa=sfa=null;
	num.k=sum.k=k;
	num.b=sum.b=b;
}
void abcd :: Push_Up()
{
	sum=ls->sum+num+rs->sum;
}
void Zig(abcd *x)
{
	abcd *y=x->fa;
	y->ls=x->rs;
	x->rs->fa=y;
	x->rs=y;
	x->fa=y->fa;
	if(y==y->fa->ls)
		y->fa->ls=x;
	else if(y==y->fa->rs)
		y->fa->rs=x;
	y->fa=x;
	y->Push_Up();
}
void Zag(abcd *x)
{
	abcd *y=x->fa;
	y->rs=x->ls;
	x->ls->fa=y;
	x->ls=y;
	x->fa=y->fa;
	if(y==y->fa->ls)
		y->fa->ls=x;
	else if(y==y->fa->rs)
		y->fa->rs=x;
	y->fa=x;
	y->Push_Up();
}
void Splay(abcd *x)
{
	while(x->fa->ls==x||x->fa->rs==x)
	{
		abcd *y=x->fa,*z=y->fa;
		if(x==y->ls)
		{
			if(y==z->ls)
				Zig(y);
			Zig(x);
		}
		else
		{
			if(y==z->rs)
				Zag(y);
			Zag(x);
		}
	}
	x->Push_Up();
}
void Access(abcd *x)
{
	abcd *y=null;
	while(x!=null)
	{
		Splay(x);
		x->rs=y;
		x->Push_Up();
		y=x;
		x=x->fa;
	}
}
abcd* Find_Root(abcd *x)
{
	abcd *y;
	Access(x);
	Splay(x);
	for(y=x;y->ls!=null;y=y->ls);
	return y;
}
int n,m,fa[M],v[M],tot;
pair<int,int>EXGCD(int x,int y)
{
	if(!y) return make_pair(1,0);
	pair<int,int>temp=EXGCD(y,x%y);
	return make_pair(temp.second,temp.first-x/y*temp.second);
}
int Inverse(int x)
{
	int temp=EXGCD((x+p)%p,p).first;
	return (temp%p+p)%p;
}
void DFS(int x)
{
	v[x]=tot;
	if(v[fa[x]]==tot)
	{
		tree[x]->sfa=tree[fa[x]];
		return ;
	}
	tree[x]->fa=tree[fa[x]];
	if(!v[fa[x]])
		DFS(fa[x]);
}
int Query(abcd *x)
{
	abcd *root=Find_Root(x);
	Access(root->sfa);
	Splay(root->sfa);
	int k=root->sfa->sum.k;
	int b=root->sfa->sum.b;
	if(k==1)
	{
		if(b==0)
			return -2;
		else
			return -1;
	}
	int temp=(p-b)*Inverse(k-1)%p;
	Access(x);
	Splay(x);
	return x->sum.F(temp);
}
void Modify(abcd *x,int k,abcd *f,int b)
{
	abcd *root=Find_Root(x);
	x->num.k=k;
	x->num.b=b;
	x->Push_Up();
	if(x==root)
		x->sfa=null;
	else
	{
		Access(x);
		Splay(x);
		x->ls->fa=null;
		x->ls=null;
		x->Push_Up();
		if(Find_Root(root->sfa)!=root)
		{
			Access(root);
			Splay(root);
			root->fa=root->sfa;
			root->sfa=null;
		}
	}
	Access(x);
	Splay(x);
	if(Find_Root(f)==x)
		x->sfa=f;
	else
		x->fa=f;
}
int main()
{
	int i,x,k,f,b;
	char o[10];
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d%d%d",&k,&f,&b);
		fa[i]=f;
		tree[i]=new abcd(k,b);
	}
	for(i=1;i<=n;i++)
		if(!v[i])
			++tot,DFS(i);
	cin>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%s",o);
		if(o[0]=='A')
			scanf("%d",&x),printf("%d\n", Query(tree[x]) );
		else
			scanf("%d%d%d%d",&x,&k,&f,&b),Modify(tree[x],k,tree[f],b);
	}
}