lp1501 国家集训队 Tree II

如果没有操作2，就是树链剖分套线段树的裸题了。
但是操作2让这题变得麻烦了很多。
考虑LCT。我们知道LCT维护每一条链使用了平衡树。仔细观察这一题的信息，我们发现它们都是可以使用平衡树来维护的。
那么，我们就可以用LCT来维护这道题。
注意：处理信息的时候要先乘再加，否则可能会引起混乱。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#define add(X,Y) (X=(X+Y)%MOD)
#define mlt(X,Y) (X=(1ll*X*Y%MOD))
using namespace std;

typedef long long ll;
inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=100005;
const ll MOD=51061;
int fa[N],ch[N][2],rev[N],sz[N];
ll sm[N],val[N],lzy1[N],lzy2[N];
inline void updt(int X){
	sz[X]=sz[ch[X][0]]+sz[ch[X][1]]+1;
	sm[X]=(sm[ch[X][0]]+sm[ch[X][1]]+val[X])%MOD;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void rnw1(int X,ll V){
	add(sm[X],1ll*V*sz[X]);
//	这里不应使用mlt，这是因为mlt会修改原数。 
	add(val[X],V);
	add(lzy1[X],V);
}
inline void rnw2(int X,ll V){
	mlt(sm[X],V);
	mlt(val[X],V);
	mlt(lzy2[X],V);
	mlt(lzy1[X],V);
}
inline void pshd(int X){
	if(lzy2[X]!=1){
		rnw2(ch[X][0],lzy2[X]);
		rnw2(ch[X][1],lzy2[X]);
		lzy2[X]=1;
	}
	if(lzy1[X]){
		rnw1(ch[X][0],lzy1[X]);
		rnw1(ch[X][1],lzy1[X]);
		lzy1[X]=0;
	}
	if(rev[X]){
		if(ch[X][0])flp(ch[X][0]);
		if(ch[X][1])flp(ch[X][1]);
		rev[X]=0;
	}
}
inline bool ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline bool fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[X]=Z,fa[Y]=X;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline void split(int X,int Y){
	chgrt(X),access(Y),splay(Y);
}
//X在Y下方。
inline void link(int X,int Y){
	chgrt(X),fa[X]=Y;
} 
inline void cut(int X,int Y){
	split(X,Y),fa[X]=ch[Y][0]=0;
}

int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		sm[i]=val[i]=lzy2[i]=1;
	}
	int X,Y,P,Q;
	ll V;
	for(int i=1;i<n;++i){
		scanf("%d%d",&X,&Y);
		link(X,Y);
	}
	char op[4];
	for(int i=1;i<=q;++i){
		std::cin>>op;
		scanf("%d%d",&X,&Y);
		switch(op[0]){
			case '+':{
				scanf("%lld",&V);
				split(X,Y);
				rnw1(Y,V);
				break;
			}
			case '-':{
				scanf("%d%d",&P,&Q);
				cut(X,Y);
				link(P,Q);
				break;
			}
			case '*':{
				scanf("%lld",&V);
				split(X,Y);
				rnw2(Y,V);
				break;
			}
			case '/':{
				split(X,Y);
				printf("%lld\n",sm[Y]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}