传送门
LCT模板题
讲一下几个细节：
1、cut的时候如果只是将(x)定为根，然后将它的右儿子以及(y)的父亲清空是错的，因为(x)此时的右儿子不一定是(y)
所以记得需要提取路径，然后再将深度小的那个节点的左儿子和深度大的节点的父亲清空
2、对于标记的问题，建议将点权表示为(p*v_i+q)的形式（(p)为乘法标记，(q)为加法标记）
那么打乘法标记的时候就是将乘法标记和加法标记一起修改，打加法标记的时候就只需要管加法标记就行了
代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10,mod=51061;char p[20];
int st[maxn],n,q,v[maxn],size[maxn],f[maxn],ch[maxn][2],sum[maxn],tag[maxn],cf[maxn],jf[maxn];
int isroot(int x){return ch[f[x]][0]!=x&&ch[f[x]][1]!=x;}
void reverse(int x){tag[x]^=1,swap(ch[x][0],ch[x][1]);}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}
void pushdown(int x){
if(tag[x]){
if(ch[x][0])reverse(ch[x][0]);
if(ch[x][1])reverse(ch[x][1]);
tag[x]^=1;
}
if(cf[x]!=1){
sum[ch[x][0]]=mul(sum[ch[x][0]],cf[x]);
sum[ch[x][1]]=mul(sum[ch[x][1]],cf[x]);
v[ch[x][0]]=mul(v[ch[x][0]],cf[x]);
v[ch[x][1]]=mul(v[ch[x][1]],cf[x]);
cf[ch[x][0]]=mul(cf[ch[x][0]],cf[x]);
cf[ch[x][1]]=mul(cf[ch[x][1]],cf[x]);
jf[ch[x][0]]=mul(jf[ch[x][0]],cf[x]);
jf[ch[x][1]]=mul(jf[ch[x][1]],cf[x]);
cf[x]=1;
}
if(jf[x]){
sum[ch[x][0]]=add(sum[ch[x][0]],mul(jf[x],size[ch[x][0]]));
sum[ch[x][1]]=add(sum[ch[x][1]],mul(jf[x],size[ch[x][1]]));
v[ch[x][0]]=add(v[ch[x][0]],jf[x]);
v[ch[x][1]]=add(v[ch[x][1]],jf[x]);
jf[ch[x][0]]=add(jf[ch[x][0]],jf[x]);
jf[ch[x][1]]=add(jf[ch[x][1]],jf[x]);
jf[x]=0;
}
}
void update(int x){
sum[x]=add(sum[ch[x][0]],add(sum[ch[x][1]],v[x]));
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void move(int x){
int fa=f[x],faa=f[fa],tmp=ch[fa][1]==x;
if(!isroot(fa))ch[faa][ch[faa][1]==fa]=x;
ch[fa][tmp]=ch[x][tmp^1],f[ch[x][tmp^1]]=fa;
ch[x][tmp^1]=fa,f[fa]=x,f[x]=faa;
update(fa),update(x);
}
void splay(int x){
int y,z=0,now=x;st[++z]=now;
while(!isroot(now))st[++z]=now=f[now];
while(z)pushdown(st[z]),z--;
while(!isroot(x)){
y=f[x],z=f[y];
if(!isroot(y)){
if((ch[y][0]==x)^(ch[z][0]==y))move(y);
else move(x);
}
move(x);
}
update(x);
}
void access(int x){
int y=0;
while(x){
splay(x),ch[x][1]=y;
update(x),y=x,x=f[x];
}
}
void makeroot(int x){access(x),splay(x),reverse(x);}
void link(int x,int y){makeroot(x),f[x]=y;}
void split(int x,int y){makeroot(x),access(y),splay(y);}
void cut(int x,int y){split(x,y);f[x]=ch[y][0]=0,update(y);}
int main()
{
read(n),read(q);for(rg int i=1;i<=n;i++)cf[i]=v[i]=1;
for(rg int i=1,x,y;i<n;i++)read(x),read(y),link(x,y);
for(rg int i=1,x,y,a,b;i<=q;i++){
scanf("%s",p+1);
if(p[1]=='+'){
read(x),read(y),read(a);
split(x,y),v[y]=add(v[y],a);
sum[y]=add(sum[y],mul(a,size[y]));
jf[y]=add(jf[y],a);
}
if(p[1]=='-')read(x),read(y),read(a),read(b),cut(x,y),link(a,b);
if(p[1]=='/')read(x),read(y),split(x,y),printf("%d
",sum[y]);
if(p[1]=='*'){
read(x),read(y),read(a);split(x,y);
sum[y]=mul(sum[y],a),v[y]=mul(v[y],a);
cf[y]=mul(cf[y],a),jf[y]=mul(jf[y],a);
}
}
}