/************************************************************** Problem: 2631 User: wangyucheng Language: C++ Result: Accepted Time:18408 ms Memory:9252 kb ****************************************************************/ #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define N 110000 #define uint unsigned int int rt[N]; int ch[N][2]; int pre[N]; uint s[N],c[N]; uint sum[N]; uint siz[N]; int rev[N]; uint val[N]; const uint mod=51061; int n,q; int nn,e[N],ne[N*2],v[N*2]; void add(int x,int y){ ne[++nn]=e[x],e[x]=nn,v[nn]=y; } void mul(int x,uint y){ if(!x)return; sum[x]=(sum[x]*y)%mod; val[x]=(val[x]*y)%mod; s[x]=(s[x]*y)%mod; c[x]=(c[x]*y)%mod; } void revs(int x){ if(!x)return; rev[x]^=1; swap(ch[x][0],ch[x][1]); } void plu(int x,uint y){ if(!x)return; val[x]=(val[x]+y)%mod; sum[x]=(siz[x]%mod*y+sum[x])%mod; s[x]=(s[x]+y)%mod; } void push(int x){ if(rev[x]){ revs(ch[x][0]); revs(ch[x][1]); rev[x]=0; } if(c[x]!=1){ mul(ch[x][0],c[x]); mul(ch[x][1],c[x]); c[x]=1; } if(s[x]){ plu(ch[x][0],s[x]); plu(ch[x][1],s[x]); s[x]=0; } } void up(int x){ sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+val[x])%mod; siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; } void rotate(int x){ int y=pre[x],z=pre[y],k=ch[y][0]==x; pre[ch[y][!k]=ch[x][k]]=y; pre[ch[x][k]=y]=x; pre[x]=z; if(!rt[y])ch[z][ch[z][1]==y]=x; else rt[y]=0,rt[x]=1; up(y); } void dfs(int x){ if(!rt[x])dfs(pre[x]); push(x); } void splay(int x){ dfs(x); int y,z; for(;!rt[x];){ y=pre[x],z=pre[y]; if(rt[y])rotate(x); else if((ch[y][1]==x)^(ch[z][1]==y))rotate(x),rotate(x); else rotate(y),rotate(x); } up(x); } int acess(int x){ int y=0; for(;x;y=x,x=pre[x]){ splay(x); rt[ch[x][1]]=1; ch[x][1]=y; rt[y]=0; up(x); } return y; } void cut(int x,int y){ acess(y); splay(x); if(pre[x]==y)pre[x]=0; else{ acess(x); splay(y); pre[y]=0; } } void makeroot(int x){ acess(x); splay(x); revs(x); } void link(int x,int y){ makeroot(x); pre[x]=y; } int qu[N],he,bo; void init(){ for(int i=1;i<=n;i++){ c[i]=1,siz[i]=1; val[i]=1; sum[i]=1; rt[i]=1; } int x; qu[he=bo=1]=1; while(he>=bo){ for(int i=e[x=qu[bo++]];i;i=ne[i]){ if(!pre[v[i]]&&v[i]!=1)pre[v[i]]=x,qu[++he]=v[i]; } } } int ask(int a,int b){ acess(a); int y=acess(b); if(y==a)return (sum[ch[a][1]]+val[a])%mod; splay(a); return (sum[ch[y][1]]+val[y]+sum[a])%mod; } void jia(int a,int b,uint z){ acess(a); z%=mod; int y=acess(b); if(y==a){ plu(ch[y][1],z); val[y]=(val[y]+z)%mod; up(y); return; } splay(a); plu(a,z); plu(ch[y][1],z); val[y]=(val[y]+z)%mod; up(y); } void cheng(int a,int b,uint z){ acess(a); int y=acess(b); z%=mod; if(y==a){ mul(ch[y][1],z); val[y]=(val[y]*z)%mod; up(y); return; } splay(a); mul(a,z); mul(ch[y][1],z); val[y]=(val[y]*z)%mod; up(y); } int main(){ scanf("%d%d",&n,&q); for(int i=1;i<n;i++){ int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); } init(); for(int i=1;i<=q;i++){ char in; int a,b,g,h; scanf(" %c",&in); if(in==‘+‘){ scanf("%d%d%d",&a,&b,&g); jia(a,b,g); } if(in==‘/‘){ scanf("%d%d",&a,&b); printf("%d\n",ask(a,b)); } if(in==‘*‘){ scanf("%d%d%d",&a,&b,&g); cheng(a,b,g); } if(in==‘-‘){ scanf("%d%d%d%d",&a,&b,&g,&h); cut(a,b); link(g,h); } } }
原文:http://www.cnblogs.com/wangyucheng/p/3731813.html