AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2631
[分析]
这题共有几种操作，很多种都是与路径有关的，还有一种就是断开与连接边．
路径有关，而且树的形态也可以改变...这不就是动态树了么...
这题中有两个tag，注意一下它们的优先顺序．怎么使得意义不会变呢?
１．当下乘标记的时候，如果这里有加标记，注意将加标记也乘上这个数；加标记时直接加即可，不用管乘标记
２．当下传标记时，先下传乘标记，再下传加标记．
那就比较简单的解决了...
[p.s.]因为这题有乘法，所以int是不能过的，如果是longlong似乎又会超时?...
于是hzwer用了unsigned int 过了？...那我们也用unsigned int 吧...
献上代码：
#include<cstdio> #include<algorithm> using namespace std; typedef unsigned int ll; const int mod=51061; const int maxn=100010; struct Node{ int l,r,f,sz; ll dt,sm; ll js,cs; bool rt,rv; bool rev(){swap(l,r);} }s[maxn]; int n,m; inline int in(){ int x=0;char ch=getchar(); while(ch>'9' || ch<'0') ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x; } inline void add(ll &x,ll y){x+=y;if(x>=mod) x-=mod;} inline void mul(ll &x,ll y){x=x*y%mod;} inline ll remul(ll x,ll y){return x*y%mod;} inline ll readd(ll x,ll y,ll z){return (x+y+z)%mod;} void push_down(int x){ if(s[x].rv){ s[x].rev();s[x].rv=0; if(s[x].l) s[s[x].l].rv^=1; if(s[x].r) s[s[x].r].rv^=1; } int ls=s[x].l,rs=s[x].r,js=s[x].js,cs=s[x].cs; if(cs!=1){ if(ls) mul(s[ls].sm,cs),mul(s[ls].cs,cs),mul(s[ls].dt,cs),mul(s[ls].js,cs); if(rs) mul(s[rs].sm,cs),mul(s[rs].cs,cs),mul(s[rs].dt,cs),mul(s[rs].js,cs); s[x].cs=1; } if(js){ if(ls) add(s[ls].sm,remul(s[ls].sz,js)),add(s[ls].js,js),add(s[ls].dt,js); if(rs) add(s[rs].sm,remul(s[rs].sz,js)),add(s[rs].js,js),add(s[rs].dt,js); s[x].js=0; } } void down_tag(int x){ if(s[x].f) down_tag(s[x].f); push_down(x); } void update(int x){ s[x].sz=s[s[x].l].sz+s[s[x].r].sz+1; s[x].sm=readd(s[s[x].l].sm,s[s[x].r].sm,s[x].dt); } void zig(int x){ int y=s[x].f;s[x].f=s[y].f; if(s[y].rt) s[y].rt=false,s[x].rt=true; else{ if(y==s[s[y].f].l) s[s[y].f].l=x; else s[s[y].f].r=x;} s[y].l=s[x].r; if(s[x].r) s[s[x].r].f=y; s[x].r=y,s[y].f=x; update(y); } void zag(int x){ int y=s[x].f;s[x].f=s[y].f; if(s[y].rt) s[y].rt=false,s[x].rt=true; else{ if(y==s[s[y].f].l) s[s[y].f].l=x; else s[s[y].f].r=x;} s[y].r=s[x].l; if(s[x].l) s[s[x].l].f=y; s[x].l=y,s[y].f=x; update(y); } void Splay(int x){ down_tag(x); int y; while(!s[x].rt){ y=s[x].f; if(s[y].rt){ if(x==s[y].l) zig(x); else zag(x);} else{ int z=s[y].f; if(y==s[z].l){ if(x==s[y].l) zig(y),zig(x); else zag(x),zig(x);} else{ if(x==s[y].r) zag(y),zag(x); else zig(x),zag(x);} } } update(x); } void Access(int x){ for(int last=0;x;x=s[last=x].f){ Splay(x); s[s[x].r].rt=true; s[s[x].r=last].rt=false; update(x); } } void make_rt(int x){ Access(x);Splay(x);s[x].rv^=1;} void Link(int v,int u){ make_rt(u); s[u].f=v; } void Cut(int v,int u){ make_rt(u); Access(v); Splay(v); s[u].f=s[v].f; s[u].rt=true; s[v].f=s[v].l=0; update(v); } void Add(int y,int x,int k){ make_rt(x); Access(y); Splay(y); add(s[y].dt,k),add(s[y].js,k); add(s[y].sm,remul(s[y].sz,k)); } void Mul(int y,int x,int k){ make_rt(x); Access(y); Splay(y); mul(s[y].dt,k),mul(s[y].cs,k); mul(s[y].sm,k),mul(s[y].js,k); } ll query(int y,int x){ make_rt(x); Access(y); Splay(y); return s[y].sm; } int main(){ #ifndef ONLINE_JUDGE freopen("2631.in","r",stdin); freopen("2631.out","w",stdout); #endif int u,v,c,u1,v1; char ord[2]; n=in();m=in(); for(int i=1;i<=n;i++) s[i].rt=s[i].dt=1; for(int i=1;i<n;i++) u=in(),v=in(),Link(u,v); while(m--){ scanf("%s",ord),u=in(),v=in(); if(ord[0]=='+') c=in(),Add(u,v,c); else if(ord[0]=='-') u1=in(),v1=in(),Cut(u,v),Link(u1,v1); else if(ord[0]=='*') c=in(),Mul(u,v,c); else printf("%d ",query(u,v)); } return 0; }