bzoj2759：一个动态树好题 （LCT+Exgcd）

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2759

题目分析：这是一道真动态树好题，不像某些其它自称好题的题目（bzoj4300“绝世好题”，其实是大水题）。

言归正传，我们来看看这道题。如果有一条方程是a=ka+b%10007的形式，且0<=a<10007，你会解a吗？很明显，当k=0时，a=b；当k=1时，若b=0，则有无穷多解，否则无解；当k>1时，用扩展欧几里得解。那么假设有两条方程：a1=k1a2+b1%10007,a2=k2a1+b2%10007，你会解a1吗？很简单，我们把前面式子的a2用后面的式子代替，然后就和刚才的一样了。而且这些式子是可以用splay进行信息合并的。

现在题目给出了很多条形如a_i=ki*a_pi+bi%10007的式子，我们认为i的父亲是pi，这样我们就得到了一棵环套树森林，然后我们任意选择一个环上的点i，将i到pi的边断掉，就变成了一个普通的森林，并且我们开一个域special_fa，令Node[i]->special_fa=pi，记录下来：

图中的实边代表树上的边，虚边代表special_fa边。很明显只有一棵树的根，special_fa才会有值。当我们要求a的值的时候，先找到它的根root，然后Access(Node[root]->special_fa)，求出Node[root]->special_fa的值，再求出root的值，再通过Access(a)，求出a的值。

现在的问题在于修改操作，假设我要改变a的父亲为p，又该怎么做呢？我们先看一下a是否为某棵树的根，是的话就断掉a的special_fa边，然后看一下p是否在a的子树中，是的话a的special_fa变为p，否则a的path_parent变为p；若a不是某棵树的根，先断掉a和它原父亲的边，然后看p是否在a的子树……（同上），最后如果a在原先的环上，还要令a的原根的special_fa边变为path_parent边。（看看上图就可以自己脑补一下了）

擅长数据结构的我这题都调了两个小时（说实话我敲LCT基本上是敲完立马过样例，一交立马AC那种），主要是有些细节一开始没有想清楚，还有码code的时候状态不是很好，出现各种错误。比如说splay信息的合并一开始搞错了；”if (F->fa)”写成了while；我在解扩展gcd的时候，为了避免负数让程序去解Exgcd(M,k-1)而不是1-k，结果最后Y忘了取反；没有判断a是根的情况；修改了k和b的值没有重新再Up()一次；给某个点打path_parent标记之前没有将它Splay等等……QAQ

CODE：

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;

const int maxn=30010;
const int M=10007;

struct Tnode
{
	int vk,vb,K,B,path_parent,special_fa;
	Tnode *fa,*son[2];
	int Get_d() { return fa->son[1]==this; }
	void Connect(Tnode *P,int d) { (son[d]=P)->fa=this; }
	void Up()
	{
		K=vk,B=vb;
		if (son[0]) B=(K*son[0]->B+B)%M,K=K*son[0]->K%M;
		if (son[1]) B=(son[1]->K*B+son[1]->B)%M,K=son[1]->K*K%M;
	}
} tree[maxn];
Tnode *Node[maxn];
int cur=-1;

int X,Y;
int n,q;

Tnode *New_node()
{
	cur++;
	tree[cur].vk=tree[cur].K=0;
	tree[cur].vb=tree[cur].B=0;
	tree[cur].path_parent=tree[cur].special_fa=0;
	tree[cur].fa=tree[cur].son[0]=tree[cur].son[1]=NULL;
	return tree+cur;
}

void Zig(Tnode *P)
{
	int d=P->Get_d();
	Tnode *F=P->fa;
	if (P->son[!d]) F->Connect(P->son[!d],d);
	else F->son[d]=NULL;
	if (F->fa) F->fa->Connect(P, F->Get_d() );
	else P->fa=NULL;
	F->Up();
	P->Connect(F,!d);
	P->path_parent=F->path_parent;
	F->path_parent=0;
}

void Splay(Tnode *P)
{
	while (P->fa)
	{
		Tnode *F=P->fa;
		if (F->fa) ( P->Get_d()^F->Get_d() )? Zig(P):Zig(F);
		Zig(P);
	}
	P->Up();
}

void Down(int x)
{
	Splay(Node[x]);
	Tnode *&tag=Node[x]->son[1];
	if (tag)
	{
		tag->fa=NULL;
		tag->path_parent=x;
		tag=NULL;
		Node[x]->Up();
	}
}

void Access(int x)
{
	Down(x);
	int y=Node[x]->path_parent;
	while (y)
	{
		Down(y);
		Node[y]->Connect(Node[x],1);
		Node[y]->Up();
		Node[x]->path_parent=0;
		x=y;
		y=Node[x]->path_parent;
	}
}

Tnode *Find_root(Tnode *P)
{
	if (!P->son[0]) return P;
	return Find_root(P->son[0]);
}

bool Judge(Tnode *P,int y)
{
	Access(y);
	Splay(Node[y]);
	return Find_root(Node[y])==P;
}

void Link(int x,int y)
{
	Splay(Node[y]);
	Node[y]->path_parent=x;
}

void Exgcd(int a,int b)
{
	if (!b)
	{
		X=1,Y=0;
		return;
	}
	Exgcd(b,a%b);
	int u=Y;
	Y=X-u*(a/b);
	X=u;
}

int Solve(int k,int b)
{
	k--;
	Exgcd(M,k);
	Y*=b;
	Y=-Y;
	Y=(Y%M+M)%M;
	return Y;
}

int main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);

	scanf("%d",&n);
	for (int i=1; i<=n; i++) Node[i]=New_node();
	for (int i=1; i<=n; i++)
	{
		int k,p,b;
		scanf("%d%d%d",&k,&p,&b);
		Node[i]->vk=k;
		Node[i]->vb=b;
		Node[i]->Up();
		if ( !Judge(Node[i],p) ) Link(p,i);
		else Node[i]->special_fa=p;
	}

	scanf("%d",&q);
	while (q--)
	{
		char c=getchar();
		while ( c!='A' && c!='C' ) c=getchar();

		if (c=='A')
		{
			int a;
			scanf("%d",&a);

			Access(a);
			Splay(Node[a]);
			Tnode *P=Find_root(Node[a]);

			int sfa=P->special_fa;
			Access(sfa);
			Splay(P);
			int k=P->K;
			int b=P->B;

			int root;
			if (!k) root=b;
			if (k==1)
			{
				if (b) printf("-1\n");
				else printf("-2\n");
				continue;
			}
			if (k>1) root=Solve(k,b);
			root=(P->vk*root+P->vb)%M;

			if (P==Node[a])
			{
				printf("%d\n",root);
				continue;
			}

			Access(a);
			Splay(P);
			k=P->son[1]->K;
			b=P->son[1]->B;
			root=(k*root+b)%M;
			printf("%d\n",root);
		}

		if (c=='C')
		{
			int a,k,p,b;
			scanf("%d%d%d%d",&a,&k,&p,&b);

			Access(a);
			Splay(Node[a]);
			Tnode *P=Find_root(Node[a]);

			if (Node[a]==P)
			{
				P->special_fa=0;
				P->vk=k;
				P->vb=b;
				P->Up();

				Access(p);
				Splay(Node[p]);
				if ( Find_root(Node[p])==P ) P->special_fa=p;
				else P->path_parent=p;
				continue;
			}

			Access(P->special_fa);
			Splay(Node[a]);
			bool flag=(Find_root(Node[a])==P);

			Access(a);
			Splay(Node[a]);
			Node[a]->son[0]->fa=NULL;
			Node[a]->son[0]->path_parent=Node[a]->path_parent;
			Node[a]->path_parent=0;
			Node[a]->son[0]=NULL;

			Node[a]->vk=k;
			Node[a]->vb=b;
			Node[a]->Up();

			if ( Judge(Node[a],p) ) Node[a]->special_fa=p;
			else Node[a]->path_parent=p;
			if ( flag && !Judge(P,p) )
			{
				Splay(P);
				P->path_parent=P->special_fa;
				P->special_fa=0;
			}
		}
	}

	return 0;
}