Description一棵n個點的樹，每個點的初始權值為1。對于這棵樹有q個操作，每個操作為以下四種操作之一： + u v c：將u到v的路徑上的點的權值都加上自然數c； - u1 v1 u2 v2：將樹中原有的邊(u1,v1)刪除，加入一條新邊(u2,v2)，保證操作完之后仍然是一棵樹； * u v c：將u到v的路徑上的點的權值都乘上自然數c； / u v：詢問u到v的路徑上的點的權值和，求出答案對于51061的余數。Input第一行兩個整數n，q 接下來n-1行每行兩個正整數u，v，描述這棵樹 接下來q行，每行描述一個操作Output對于每個/對應的答案輸出一行Sample Input3 2 1 2 2 3 * 1 3 4 / 1 1Sample Output4Hint數據規模： 10%的數據保證，1<=n，q<=2000 另外15%的數據保證，1<=n，q<=5 * 10^4，沒有-操作，并且初始樹為一條鏈 另外35%的數據保證，1<=n，q<=5 * 10^4，沒有-操作 100%的數據保證，1<=n，q<=10^5，0<=c<=10^4

正解：link-cut tree。

毒瘤數據結構題，調了我一下午。。主要是加和乘的lazy標記，下放時如果是乘，那么加的那個標記也要同乘，并且要先下放乘的標記，再下放加的標記。

//It is made by wfj_2048~#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <map>#include <set>#define inf (1<<30)#define r64 (51061)#define N (100010)#define il inline#define RG register#define uint unsigned int#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)using namespace std;uint ch[N][2],fa[N],size[N],lazy[N],st[N],rev1[N],rev2[N],val[N],sum[N],n,q;char s[5];il uint gi(){    RG uint x=0,q=1; RG char ch=getchar(); while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();    if (ch=='-') q=-1,ch=getchar(); while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x;}il void pushdown(RG uint x){    RG uint &l=ch[x][0],&r=ch[x][1];    if (lazy[x]) lazy[x]=0,lazy[l]^=1,lazy[r]^=1,swap(l,r);    if (rev2[x]!=1){	(val[l]*=rev2[x])%=r64,(val[r]*=rev2[x])%=r64;	(sum[l]*=rev2[x])%=r64,(sum[r]*=rev2[x])%=r64;	(rev1[l]*=rev2[x])%=r64,(rev1[r]*=rev2[x])%=r64;	(rev2[l]*=rev2[x])%=r64,(rev2[r]*=rev2[x])%=r64,rev2[x]=1;    }    if (rev1[x]){	(val[l]+=rev1[x])%=r64,(val[r]+=rev1[x])%=r64;	(sum[l]+=rev1[x]*(size[l]%r64))%=r64,(sum[r]+=rev1[x]*(size[r]%r64))%=r64;	(rev1[l]+=rev1[x])%=r64,(rev1[r]+=rev1[x])%=r64,rev1[x]=0;    }    return;}il void pushup(RG uint x){    sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%r64;    size[x]=size[ch[x][0]]+size[ch[x][1]]+1; return;}il uint isroot(RG uint x){ return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x; }il void rotate(RG uint x){    RG uint y=fa[x],z=fa[y],k=ch[y][0]==x; if (!isroot(y)) ch[z][ch[z][1]==y]=x; fa[x]=z;    ch[y][k^1]=ch[x][k],fa[ch[x][k]]=y,ch[x][k]=y,fa[y]=x,pushup(y),pushup(x); return;}il void splay(RG uint x){    RG uint top=0; st[++top]=x;    for (RG uint i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];    while (top) pushdown(st[top--]);    while (!isroot(x)){	RG uint y=fa[x],z=fa[y];	if (!isroot(y)){ if ((ch[z][0]==y)^(ch[y][0]==x)) rotate(x); else rotate(y); }	rotate(x);    }    return;}il void access(RG uint x){ RG uint t=0; while (x) splay(x),ch[x][1]=t,pushup(x),t=x,x=fa[x]; return; }il void split(RG uint x){ access(x),splay(x); return; }il void makeroot(RG uint x){ split(x),lazy[x]^=1; return; }il void link(RG uint x,RG uint y){ makeroot(x),fa[x]=y; return; }il void cut(RG uint x,RG uint y){ makeroot(x),split(y),ch[y][0]=fa[x]=0,pushup(y); return; }il void add(RG uint x,RG uint y,RG uint v){    makeroot(x),split(y),(rev1[y]+=v)%=r64,(val[y]+=v)%=r64,(sum[y]+=v*(size[y]%r64))%=r64; return;}il void times(RG uint x,RG uint y,RG uint v){    makeroot(x),split(y),(rev1[y]*=v)%=r64,(rev2[y]*=v)%=r64,(val[y]*=v)%=r64,(sum[y]*=v)%=r64; return;}il uint query(RG uint x,RG uint y){ makeroot(x),split(y); return sum[y]; }il void work(){    n=gi(),q=gi(); RG uint u,v,c; for (RG uint i=1;i<=n;++i) sum[i]=val[i]=rev2[i]=size[i]=1;    for (RG uint i=1;i<n;++i) u=gi(),v=gi(),link(u,v);    for (RG uint i=1;i<=q;++i){	scanf("%s",s); if (s[0]=='+') u=gi(),v=gi(),c=gi(),add(u,v,c);	if (s[0]=='-') u=gi(),v=gi(),cut(u,v),u=gi(),v=gi(),link(u,v);	if (s[0]=='*') u=gi(),v=gi(),c=gi(),times(u,v,c);	if (s[0]=='/'){ u=gi(),v=gi(); PRintf("%u/n",query(u,v)); }    }    return;}int main(){    File("tree");    work();    return 0;}