【题意】给定n个点的树，每个点初始权值为1，m次操作：1.x到y的点加值，2.断一条边并连一条边，保证仍是树，3.x到y的点乘值，4.x到y的点权值和取模。n,m<=10^5。
【算法】Link-Cut Tree
【题解】区间加和区间乘标记的处理：【BZOJ】1798: [Ahoi2009]Seq 维护序列seq 线段树
splay上维护要注意：
1.上传时加本身。
2.改值的时候不能影响到0点。
3.所有改变点的儿子的地方都要上传，所有改变点的父亲的地方都要下传。
除了rotate，还有access的时候要上传up。
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define int unsigned int using namespace std; int read(){ int s=0,t=1;char c; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}while(isdigit(c=getchar())); return s*t; } const int maxn=100010,MOD=51061; int n,Q,sum[maxn],A[maxn],B[maxn],g[maxn],a[maxn],sz[maxn],t[maxn][2],f[maxn],N[maxn]; int M(int x){return x>=MOD?x-MOD:x;} void up(int x){sum[x]=M(M(sum[t[x][0]]+sum[t[x][1]])+a[x]);sz[x]=sz[t[x][0]]+sz[t[x][1]]+1;} void modify_a(int k,int x){ if(!k)return; a[k]=M(a[k]+x); sum[k]=M(sum[k]+sz[k]*x%MOD); A[k]=M(A[k]+x); }//make 0 no influence void modify_b(int k,int x){ if(!k)return; a[k]=a[k]*x%MOD; sum[k]=sum[k]*x%MOD;A[k]=A[k]*x%MOD;B[k]=B[k]*x%MOD; } void down(int k){ if(g[k]){ swap(t[k][0],t[k][1]); if(t[k][0])g[t[k][0]]^=1; if(t[k][1])g[t[k][1]]^=1; g[k]=0; } if(B[k]!=1){ modify_b(t[k][0],B[k]);modify_b(t[k][1],B[k]); B[k]=1; } if(A[k]){ modify_a(t[k][0],A[k]);modify_a(t[k][1],A[k]); A[k]=0; } } bool isroot(int x){return !x||(t[f[x]][0]!=x&&t[f[x]][1]!=x);} void rotate(int y){ int x=f[y]; int k=y==t[x][0]; t[x][!k]=t[y][k];f[t[y][k]]=x; if(!isroot(x))t[f[x]][x==t[f[x]][1]]=y;f[y]=f[x];f[x]=y; t[y][k]=x; up(x);up(y); } void splay(int x){ int top=x,tot=1;N[1]=x; while(!isroot(top))top=f[top],N[++tot]=top; for(int i=tot;i>=1;i--)down(N[i]); while(!isroot(x)){ if(isroot(f[x])){rotate(x);break;} int X=x==t[f[x]][1],Y=f[x]==t[f[f[x]]][1]; if(X^Y)rotate(x),rotate(x); else rotate(f[x]),rotate(x); } } void access(int x){ int y=0; while(x){ splay(x); t[x][1]=y; up(x);/// y=x;x=f[x]; } } void reserve(int x){access(x);splay(x);g[x]^=1;} void link(int x,int y){reserve(x);f[x]=y;} void find(int x,int y){reserve(x);access(y);splay(y);} void cut(int x,int y){find(x,y);t[y][0]=f[x]=0;} char s[10]; #undef int int main(){ #define int unsigned int n=read();Q=read(); for(int i=1;i<=n;i++)sum[i]=a[i]=1,sz[i]=1,A[i]=0,B[i]=1; for(int i=1;i<n;i++)link(read(),read()); while(Q--){ scanf("%s",s); int x=read(),y=read(); if(s[0]=='+'){ int z=read(); find(x,y);modify_a(y,z); } if(s[0]=='-'){ int u=read(),v=read(); cut(x,y);link(u,v); } if(s[0]=='*'){ int z=read(); find(x,y);modify_b(y,z); } if(s[0]=='/'){ find(x,y);printf("%d ",sum[y]); } } return 0; }