状态奇差无比，sbt都能错一遍。
不动笔光想没有想到怎么做，画图之后发现一个很明显的性质……
那就是两个开战的部落，其中一个是另一个的父亲。
所以在儿子那里加个权值。查询的时候树链剖分查询链上点权和，减去lca的点权（因为lca那如果有点权，代表的是lca和lca的父亲之间的那条边）。
#include<cstdio> #include<algorithm> #include<cctype> #include<cstring> #include<cstdlib> #define left (rt<<1) #define right (rt<<1|1) #define mid ((l+r)>>1) #define lson l,mid,left #define rson mid+1,r,right #define maxn 300050 using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch==‘-‘) f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-‘0‘; ch=getchar(); } return num*f; } struct Edge{ int next,to; }edge[maxn*3]; int head[maxn],num; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } int tree[maxn*4]; int dfn[maxn]; int deep[maxn]; int father[maxn]; int size[maxn]; int top[maxn]; int son[maxn]; int ID,n,m; void unifnd(int x,int fa){ deep[x]=deep[fa]+1; size[x]=1; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(to==fa) continue; father[to]=x; unifnd(to,x); size[x]+=size[to]; if(son[x]==0||size[son[x]]<size[to]) son[x]=to; } } void unionn(int x,int Top){ dfn[x]=++ID; top[x]=Top; if(son[x]==0) return; unionn(son[x],Top); for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(to==father[x]||to==son[x]) continue; unionn(to,to); } } inline void pushup(int rt){ tree[rt]=tree[left]+tree[right]; } void update(int o,int num,int l,int r,int rt){ if(l==r){ tree[rt]+=num; return; } if(o<=mid) update(o,num,lson); else update(o,num,rson); pushup(rt); return; } int query(int from,int to,int l,int r,int rt){ if(from<=l&&to>=r) return tree[rt]; int ans=0; if(from<=mid) ans+=query(from,to,lson); if(to>mid) ans+=query(from,to,rson); return ans; } struct War{ int from,to; }q[maxn];int cnt; inline void adds(int from,int to){ if(deep[from]<deep[to]) swap(from,to); q[++cnt]=(War){from,to}; update(dfn[from],1,1,n,1); return; } inline void del(int rnk){ int from=q[rnk].from; update(dfn[from],-1,1,n,1); } inline int LCA(int from,int to){ while(top[from]!=top[to]){ if(deep[top[from]]<deep[top[to]]) swap(from,to); from=father[top[from]]; } if(deep[from]>deep[to]) swap(from,to); return from; } inline int ask(int from,int to){ int lca=LCA(from,to),ans=-query(dfn[lca],dfn[lca],1,n,1); while(top[from]!=top[to]){ if(deep[top[from]]<deep[top[to]]) swap(from,to); ans+=query(dfn[top[from]],dfn[from],1,n,1); if(ans>0) return 0; from=father[top[from]]; } if(deep[from]>deep[to]) swap(from,to); ans+=query(dfn[from],dfn[to],1,n,1); if(ans>0) return 0; return 1; } int main(){ n=read(),m=read(); for(int i=1;i<n;++i){ int x=read(),y=read(); add(x,y); add(y,x); } unifnd(1,1); unionn(1,1); for(int i=1;i<=m;++i){ char c[10]; scanf("%s",c); if(c[0]==‘Q‘){ int x=read(),y=read(); if(ask(x,y)) printf("Yes\n"); else printf("No\n"); } else if(c[0]==‘C‘){ int x=read(),y=read(); adds(x,y); } else{ int x=read(); del(x); } } return 0; }