题面传送门 树剖裸题，感觉难度虚高。 当两个部落开战时，我们就把下面那个点的权值设为 1 1 1，休战则设为 0 0 0即可。 这样有一个好处就是查询时如果有 1 1 1可以直接跳出。 其他基本操作。 代码实现:
#include<cstdio> #include<cstring> using namespace std; int n,m,k,f[600039],x[300039],y[300039],hxy,sx,sy,sz,idea,id[300039],top[300039],d[300039],fa[300039],siz[300039],son[300039]; char _s; struct yyy{int to,z;}; struct ljb{ int head,h[300039]; yyy f[600039]; inline void add(int x,int y){ f[++head]=(yyy){y,h[x]}; h[x]=head; } }s; inline void get(int x,int y){while(x<=n) f[x]+=y,x+=x&-x;} inline int find(int x){int ans=0;while(x)ans+=f[x],x-=x&-x;return ans;} inline void dfs1(int x,int last){ fa[x]=last; d[x]=d[last]+1; siz[x]=1; int cur=s.h[x],pus=-1; yyy tmp; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to!=last){ dfs1(tmp.to,x); siz[x]+=siz[tmp.to]; if(siz[tmp.to]>pus) pus=siz[tmp.to],son[x]=tmp.to; } cur=tmp.z; } } inline void dfs2(int x,int last){ top[x]=last; id[x]=++idea; int cur=s.h[x]; yyy tmp; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to==son[x]) dfs2(tmp.to,last); cur=tmp.z; } cur=s.h[x]; while(cur!=-1){ tmp=s.f[cur]; if(tmp.to!=fa[x]&&tmp.to!=son[x]) dfs2(tmp.to,tmp.to); cur=tmp.z; } } inline void swap(int &x,int &y){x^=y,y^=x,x^=y;} inline void find1(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); ans=find(id[x])-find(id[top[x]]-1); if(ans){putchar('N'),putchar('o'),putchar('\n');return;} x=fa[top[x]]; } if(d[x]>d[y]) swap(x,y); ans=find(id[y])-find(id[x]); if(ans){putchar('N'),putchar('o'),putchar('\n');return;} putchar('Y'),putchar('e'),putchar('s'),putchar('\n'); } inline void get1(int x,int y){ if(d[x]>d[y]) swap(x,y); get(id[y],1); } inline void get2(int x,int y){ if(d[x]>d[y]) swap(x,y); get(id[y],-1); } inline void read(int &x){ char s=getchar();x=0; while(s<'0'||s>'9') s=getchar(); while(s>='0'&s<='9') x=(x<<3)+(x<<1)+(s^48),s=getchar(); } int main(){ register int i; memset(s.h,-1,sizeof(s.h)); read(n);read(m); for(i=1;i<n;i++) read(sx),read(sy),s.add(sx,sy),s.add(sy,sx); dfs1(1,0); dfs2(1,1); for(i=1;i<=m;i++){ _s=getchar(); while(_s<'A'||_s>'Z') _s=getchar(); if(_s=='Q'){ read(sx),read(sy); find1(sx,sy); } else if(_s=='C'){ read(sx);read(sy); x[++hxy]=sx;y[hxy]=sy; get1(sx,sy); } else{ read(sx); get2(x[sx],y[sx]); } } }