显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=100010,M=30000010,mod=1<<14;
int n,Q,cnt,fir[N],nxt[N*2],to[N*2];
int sz[N],son[N],fa[N],dep[N],nrt;
int top[N],id[N],ed[N],tot;
int rt[N],ch[M][2],sum[M],add[M],len[M];
void addedge(int a,int b){
nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;
}
void DFS(int x){
sz[x]=1;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]){
fa[to[i]]=x;dep[to[i]]=dep[x]+1;
DFS(to[i]);sz[x]+=sz[to[i]];
if(sz[son[x]]<sz[to[i]])
son[x]=to[i];
}
}
void DFS(int x,int tp){
id[x]=++tot;top[x]=tp;
if(son[x])DFS(son[x],tp);
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
DFS(to[i],to[i]);
ed[x]=tot;
}
#define ls ch[x][0]
#define rs ch[x][1]
#define lps ch[pre][0]
#define rps ch[pre][1]
#define mid ((l+r)>>1)
int Newnode(int l,int p=0){
len[++tot]=l;
if(p){
ch[tot][0]=ch[p][0];
ch[tot][1]=ch[p][1];
sum[tot]=sum[p];
add[tot]=add[p];
}
return tot;
}
void Push_up(int x){sum[x]=(sum[ls]+sum[rs])%mod;}
void Add(int x,int k){(sum[x]+=len[x]*k%mod)%=mod;(add[x]+=k)%=mod;}
void Push_down(int x,int l,int r){
if(add[x]){
ls=Newnode(mid-l+1,ls);
rs=Newnode(r-mid,rs);
Add(ls,add[x]);
Add(rs,add[x]);
add[x]=0;
}
}
int Query(int x,int l,int r,int a,int b){
if(!x||l>=a&&r<=b)return sum[x];
int ret=0;Push_down(x,l,r);
if(mid>=a)ret=Query(ls,l,mid,a,b);
if(mid<b)ret+=Query(rs,mid+1,r,a,b);
return ret;
}
int Solve(int x,int y){
int ret=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
(ret+=Query(nrt,1,n,id[top[x]],id[x]))%=mod;
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
(ret+=Query(nrt,1,n,id[y],id[x]))%=mod;
return ret%mod;
}
void Clr(int pre,int &x,int l,int r,int a,int b){
Push_down(pre,l,r);
x=Newnode(r-l+1,pre);
if(l>=a&&r<=b){x=0;return;}
if(mid>=a)Clr(lps,ls,l,mid,a,b);
if(mid<b)Clr(rps,rs,mid+1,r,a,b);
Push_up(x);
}
void Clear(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Clr(nrt,nrt,1,n,id[top[x]],id[x]);x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
Clr(nrt,nrt,1,n,id[y],id[x]);
}
void Update(int pre,int &x,int l,int r,int a,int b,int k){
Push_down(pre,l,r);
x=Newnode(r-l+1,pre);
if(l>=a&&r<=b){Add(x,k);return;}
if(mid>=a)Update(lps,ls,l,mid,a,b,k);
if(mid<b)Update(rps,rs,mid+1,r,a,b,k);
Push_up(x);
}
void Modify(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Update(nrt,nrt,1,n,id[top[x]],id[x],k);
x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
Update(nrt,nrt,1,n,id[y],id[x],k);
}
int a,b,k;
char op[5];
int main(){
freopen("great_tree.in","r",stdin);
freopen("great_tree.out","w",stdout);
scanf("%d%d",&n,&Q);
for(int i=1;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
}
DFS(1);DFS(1,1);tot=0;
for(int t=1;t<=Q;t++){
scanf("%s",op);
if(op[0]=='B'){
scanf("%d%d",&a,&k);
Update(nrt,nrt,1,n,id[a],ed[a],k%mod);
}
else if(op[0]=='C'){
scanf("%d%d%d",&a,&b,&k);
Modify(a,b,k%mod);
}
else if(op[0]=='Q'){
scanf("%d%d",&a,&b);
printf("%d\n",Solve(a,b));
}
else if(op[0]=='E'){
scanf("%d%d",&a,&b);
Clear(a,b);
}
else{
scanf("%d",&k);
nrt=rt[k];
}
rt[t]=nrt;
}
return 0;
}
TenderRun