Tsinsen A1303. tree(伍一鸣) LCT

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long int LL; const int maxn=100100; const LL mod=51061; int ch[maxn][2],pre[maxn]; bool rev[maxn],rt[maxn]; LL size[maxn],key[maxn],add[maxn],mul[maxn],sum[maxn]; void update_add(int r,LL d) { if(!r) return ; if(d==0) return ; key[r]=(key[r]+d)%mod; add[r]=(add[r]+d)%mod; sum[r]=(size[r]*d+sum[r])%mod; } void update_mul(int r,LL d) { if(!r) return ; if(d==1) return ; sum[r]=(sum[r]*d)%mod; key[r]=(key[r]*d)%mod; mul[r]=(mul[r]*d)%mod; add[r]=(add[r]*d)%mod; } void update_rev(int r) { if(!r) return ; swap(ch[r][0],ch[r][1]); rev[r]=rev[r]^1; } void push_down(int r) { if(!r) return ; if(rev[r]) { if(ch[r][0]) update_rev(ch[r][0]); if(ch[r][1]) update_rev(ch[r][1]); rev[r]=0; } if(mul[r]!=1) { if(ch[r][0]) update_mul(ch[r][0],mul[r]); if(ch[r][1]) update_mul(ch[r][1],mul[r]); mul[r]=1; } if(add[r]) { if(ch[r][0]) update_add(ch[r][0],add[r]); if(ch[r][1]) update_add(ch[r][1],add[r]); add[r]=0; } } void push_up(int r) { sum[r]=key[r]%mod; size[r]=1; if(ch[r][0]) { sum[r]=(sum[r]+sum[ch[r][0]])%mod; size[r]+=size[ch[r][0]]; } if(ch[r][1]) { sum[r]=(sum[r]+sum[ch[r][1]])%mod; size[r]+=size[ch[r][1]]; } } void Rotate(int x) { int y=pre[x],kind=ch[y][1]==x; ch[y][kind]=ch[x][!kind]; pre[ch[y][kind]]=y; pre[x]=pre[y]; pre[y]=x; ch[x][!kind]=y; if(rt[y]) rt[y]=false,rt[x]=true; else ch[pre[x]][ch[pre[x]][1]==y]=x; push_up(y); } void P(int r) { if(!rt[r]) P(pre[r]); push_down(r); } void Splay(int r) { P(r); while(!rt[r]) { int f=pre[r],ff=pre[f]; if(rt[f]) Rotate(r); else if((ch[ff][1]==f)==(ch[f][1]==r)) Rotate(f),Rotate(r); else Rotate(r),Rotate(r); } push_up(r); } int Access(int x) { int y=0; for(;x;x=pre[y=x]) { Splay(x); rt[ch[x][1]]=true; rt[ch[x][1]=y]=false; push_up(x); } return y; } void mroot(int r) { Access(r); Splay(r); update_rev(r); } void link(int u,int v) { mroot(u); pre[u]=v; } void cut(int u,int v) { mroot(u); Splay(v); pre[ch[v][0]]=pre[v]; pre[v]=0; rt[ch[v][0]]=true; ch[v][0]=0; push_up(v); } void Add(int u,int v,LL d) { mroot(u); Access(v); Splay(v); update_add(v,d); } void Mul(int u,int v,LL d) { mroot(u); Access(v); Splay(v); update_mul(v,d); } void debug(); void query(int u,int v) { mroot(u); Access(v); Splay(v); //cout<<"size: "<<size[v]<<" sum: "<<sum[v]<<endl; printf("%lld ",sum[v]); } struct Edge { int to,next; }edge[maxn*2]; int Adj[maxn],Size; void add_edge(int u,int v) { edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++; } int n,q; void init() { Size=0; for(int i=0;i<=n+10;i++) { Adj[i]=⑴; ch[i][0]=ch[i][1]=0; pre[i]=0; rt[i]=true; rev[i]=false; key[i]=1; size[i]=1; add[i]=0; mul[i]=1; sum[i]=1; } } void dfs(int u) { for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(pre[v]!=0) continue; pre[v]=u; dfs(v); } } void showit(int x) { if(x) { push_down(x); showit(ch[x][0]); printf("结点: %2d 左儿子: %2d 右儿子: %2d 父结点: %2d size: %2lld sum: %2lld key: %2lld ", x,ch[x][0],ch[x][1],pre[x],size[x],sum[x],key[x]); showit(ch[x][1]); } } void debug() { for(int i=0;i<=n;i++) { if(rt[i]) { cout<<"ROOT: "<<i<<endl; showit(i); cout<<".......... "; } } } int main() { while(scanf("%d%d",&n,&q)!=EOF) { init(); for(int i=0;i<n⑴;i++) { int u,v; scanf("%d%d",&u,&v); add_edge(u,v); add_edge(v,u); } pre[1]=⑴; dfs(1); pre[1]=0; //debug(); char op[10]; while(q--) { scanf("%s",op); if(op[0]=='+') { int u,v,c; scanf("%d%d%d",&u,&v,&c); Add(u,v,c); } else if(op[0]=='-') { int u1,v1,u2,v2; scanf("%d%d%d%d",&u1,&v1,&u2,&v2); cut(u1,v1); link(u2,v2); } else if(op[0]=='*') { int u,v,c; scanf("%d%d%d",&u,&v,&c); Mul(u,v,c); } else if(op[0]=='/') { int u,v; scanf("%d%d",&u,&v); query(u,v); } //debug(); } } return 0; }