显示代码纯文本
#define MAXN 100010UL
#define MAXT 20000010UL
#define MAXC 10UL
#define Ander 16383L
#include <stdio.h>
struct Edge{int v,nx;};
Edge edge[MAXN<<1];
int n,ec,q,dfs_clock,cnt,current,root_cnt,posl,posr,update_val,op_root[MAXN],depth[MAXN],headlist[MAXN],siz[MAXN],top[MAXN],son[MAXN],fa[MAXN],dfn[MAXN],ots[MAXN],root[MAXT],ch[MAXT][2],mark[MAXT],tree[MAXT];
char op[MAXC];
inline int in(){
int x=0,c=getchar();
while(c<'0'||c>'9') c=getchar();
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
return x;
}
inline void Add_Edge(int u,int v){
edge[++ec].v=v;
edge[ec].nx=headlist[u];
headlist[u]=ec;
return;
}
inline void ReadIn(){
n=in();q=in();
for(int i=1,a,b;i<n;i++){
a=in();b=in();
Add_Edge(a,b);
Add_Edge(b,a);
}
return;
}
inline void dfs1(int p){
siz[p]|=1;
for(int i=headlist[p];i;i=edge[i].nx){
if(fa[p]==edge[i].v) continue;
fa[edge[i].v]=p;
depth[edge[i].v]=depth[p]+1;
dfs1(edge[i].v);
siz[p]+=siz[edge[i].v];
if(siz[edge[i].v]>siz[son[p]]) son[p]=edge[i].v;
}
return;
}
inline void dfs2(int p,int tp){
top[p]=tp;
dfn[p]=++dfs_clock;
if(son[p]) dfs2(son[p],tp);
for(int i=headlist[p];i;i=edge[i].nx){
if(edge[i].v==fa[p]||edge[i].v==son[p]) continue;
dfs2(edge[i].v,edge[i].v);
}
ots[p]=dfs_clock;
return;
}
inline void Build(int l,int r,int &id){
id=++cnt;
if(l==r) return;
int mid=(l+r)>>1;
Build(l,mid,ch[id][0]);
Build(mid+1,r,ch[id][1]);
return;
}
inline void PreWork(){
dfs1(1);
dfs2(1,1);
Build(1,n,root[0]);
return;
}
inline void Clear(int l,int r,int rt){
if(mark[rt]==0||l==r) return;
int mid=(l+r)>>1;
tree[++cnt]=tree[ch[rt][0]];
mark[cnt]=mark[ch[rt][0]];
ch[cnt][0]=ch[ch[rt][0]][0];
ch[cnt][1]=ch[ch[rt][0]][1];
ch[rt][0]=cnt;
tree[++cnt]=tree[ch[rt][1]];
mark[cnt]=mark[ch[rt][1]];
ch[cnt][0]=ch[ch[rt][1]][0];
ch[cnt][1]=ch[ch[rt][1]][1];
ch[rt][1]=cnt;
if(mark[rt]==-1){
tree[ch[rt][0]]=0;
tree[ch[rt][1]]=0;
mark[ch[rt][0]]=-1;
mark[ch[rt][1]]=-1;
}
else{
tree[ch[rt][0]]+=(mid-l+1LL)*mark[rt];
tree[ch[rt][1]]+=(r-mid)*mark[rt];
tree[ch[rt][0]]&=Ander;
tree[ch[rt][1]]&=Ander;
if(mark[ch[rt][0]]==-1) mark[ch[rt][0]]=mark[rt];
else if(mark[rt]!=-1) mark[ch[rt][0]]+=mark[rt];
else mark[ch[rt][0]]=-1;
if(mark[ch[rt][1]]==-1) mark[ch[rt][1]]=mark[rt];
else if(mark[rt]!=-1) mark[ch[rt][1]]+=mark[rt];
else mark[ch[rt][1]]=-1;
}
mark[rt]=0;
return;
}
inline void Update(int l,int r,int p,int &now){
now=++cnt;
Clear(l,r,p);
if(posl<=l&&posr>=r){
ch[now][0]=ch[p][0];
ch[now][1]=ch[p][1];
mark[now]=(update_val+mark[p])&Ander;
tree[now]=tree[p]+(r-l+1LL)*update_val;
return;
}
int mid=(l+r)>>1;
if(posl<=mid) Update(l,mid,ch[p][0],ch[now][0]);
else ch[now][0]=ch[p][0];
if(posr>mid) Update(mid+1,r,ch[p][1],ch[now][1]);
else ch[now][1]=ch[p][1];
tree[now]=tree[ch[now][0]]+tree[ch[now][1]];
tree[now]&=Ander;
return;
}
inline void Div(int l,int r,int p,int &now){
now=++cnt;
Clear(l,r,p);
if(posl<=l&&posr>=r){
ch[now][0]=ch[p][0];
ch[now][1]=ch[p][1];
mark[now]=-1;
tree[now]=0;
return;
}
int mid=(l+r)>>1;
if(posl<=mid) Div(l,mid,ch[p][0],ch[now][0]);
else ch[now][0]=ch[p][0];
if(posr>mid) Div(mid+1,r,ch[p][1],ch[now][1]);
else ch[now][1]=ch[p][1];
tree[now]=tree[ch[now][0]]+tree[ch[now][1]];
tree[now]&=Ander;
return;
}
inline int Query(int l,int r,int rt){
Clear(l,r,rt);
if(posl<=l&&posr>=r) return tree[rt];
int mid=(l+r)>>1,Ans=0;
if(posl<=mid) Ans+=Query(l,mid,ch[rt][0]),Ans&=Ander;
if(posr>mid) Ans+=Query(mid+1,r,ch[rt][1]),Ans&=Ander;
return Ans;
}
inline int Q(int l,int r){
if(l>r) return 0LL;
posl=l,posr=r;
return Query(1,n,root[current]);
}
inline void Sub(int l,int r){
if(l>r) return;
posl=l,posr=r;
Div(1,n,root[current],root[++root_cnt]);
current=root_cnt;
return;
}
inline void Modify(int l,int r,int delta){
if(l>r) return;
posl=l,posr=r;
update_val=delta;
Update(1,n,root[current],root[++root_cnt]);
current=root_cnt;
return;
}
inline void BWork(){
int x,delta;
x=in();delta=in();
Modify(dfn[x],ots[x],delta);
return;
}
inline void CWork(){
int x,y,delta;
x=in();y=in();delta=in();
if(depth[x]<depth[y]) x^=y,y^=x,x^=y;
while(top[x]!=top[y]){
Modify(dfn[top[x]],dfn[x],delta);
x=fa[top[x]];
}
Modify(dfn[y],dfn[x],delta);
return;
}
inline int QWork(){
int x,y,Ans=0;
x=in();y=in();
if(depth[x]<depth[y]) x^=y,y^=x,x^=y;
while(top[x]!=top[y]){
Ans+=Q(dfn[top[x]],dfn[x]);
Ans&=Ander;
x=fa[top[x]];
}
Ans+=Q(dfn[y],dfn[x]);
return Ans&Ander;
}
inline void EWork(){
int x,y;
x=in();y=in();
if(depth[x]<depth[y]) x^=y,y^=x,x^=y;
while(top[x]!=top[y]){
Sub(dfn[top[x]],dfn[x]);
x=fa[top[x]];
}
Sub(dfn[y],dfn[x]);
return;
}
inline void Answer(){
for(int i=1;i<=q;i++){
scanf("%s",op);
if(op[0]=='B') BWork();
else if(op[0]=='C') CWork();
else if(op[0]=='Q') printf("%d\n",QWork());
else if(op[0]=='E') EWork();
else if(op[0]=='R') current=op_root[in()];
op_root[i]=current;
}
return;
}
int main(){
freopen("great_tree.in","r",stdin);
freopen("great_tree.out","w",stdout);
ReadIn();
PreWork();
Answer();
return 0;
}
stdafx.h