题目大意：给定n个形如xi=ki*x_pi+bi mod p的同余方程组 支持修改操作和求解操作

确实好题 感谢此题作者 顺便吐槽一下作者的Splay不加空节点太蛋疼了0.0

将每个点i的父亲设为pi 我们将会得到一座基环树林 将环上的一条边拆掉，在边的起始节点新开个域special_father记录这条边(P.S:好浪费 但是没办法)

于是我们得到了一座森林 显然可以用LCT来维护 每个节点的权值是个二元组(k,b)，记录每个点关于答案的线性关系，合并时左侧代入右侧中

查询时将root的special_father进行Access+Splay操作 然后借助这个环通过EXGCD求出root->special_father的值 然后Access+Splay(x)代入出解

若环上k=1 讨论b 若b=0则无穷多解 否则无解 注意k=0时要加一些处理 正常求EXGCD求不出来

单点修改 有向图 没有标记 爽爆了！

修改x的父节点时需要讨论：

首先切掉原先的父节点

如果x是所在树的根 直接切掉special_father

如果x不是根，切掉x与父节点的联系，然后讨论x是否在环上

设x所在树的根节点为root

若root->special_father所在树的根不为root 则x在环上 将root的special_father变为root的fa节点

否则切断父节点完毕

然后讨论新的父节点f是否在x的子树中

若在，将x的special_father设为f

若不在，将x的fa设为f

好题……RE一晚上……居然忘了对LCT中的任意节点进行修改操作都要先Access+Splay了……居然直接把爸爸换了……RE到死啊

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define M 30300#define p 10007using 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);	}}

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