记录编号	466426	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[洛谷3950]部落冲突	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	9.089 s
提交时间	2017-10-29 06:22:41	内存使用	18.03 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct edge{int e;edge *n;}*pre[300005];
inline void insert(int s,int e){edge *tmp(new edge);tmp->e=e;tmp->n=pre[s];pre[s]=tmp;}
int n,m,war,whi[300005];
int fa[300005],son[300005],size[300005],dep[300005];
inline void dfs1(int u){
	size[u]=1;son[u]=0;
	for(edge *i=pre[u];i;i=i->n){
		int e(i->e);if(e==fa[u])continue;
		fa[e]=u;dep[e]=dep[u]+1;dfs1(e);
		size[u]+=size[e];if(size[e]>size[son[u]])son[u]=e;
	}
}
int cnt,top[300005],id[300005],pos[300005];
inline void dfs2(int u,int rt){
	top[u]=rt;id[u]=++cnt;pos[cnt]=u;if(son[u])dfs2(son[u],rt);
	for(edge *i=pre[u];i;i=i->n){int e(i->e);if(e==fa[u]||e==son[u])continue;dfs2(e,e);}
}
int sum[1200005];
inline void pushup(int i){sum[i]=sum[i<<1]+sum[i<<1|1];}
inline void update(int pos,int w,int l,int r,int i){
	if(l==r){sum[i]+=w;return;}int mid((l+r)>>1);
	if(pos<=mid)update(pos,w,l,mid,i<<1);else update(pos,w,mid+1,r,i<<1|1);pushup(i);
}
inline int query(int ll,int rr,int l,int r,int i){
	if(ll<=l&&r<=rr)return sum[i];int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret+=query(ll,rr,l,mid,i<<1);if(mid<rr)ret+=query(ll,rr,mid+1,r,i<<1|1);return ret;
}
inline bool check(int x,int y){
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(query(id[top[x]],id[x],1,n,1)>0)return false;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	if(id[x]^id[y])return query(id[x]+1,id[y],1,n,1)<=0;
	else return true;
}
char op[2];
int main(){
	freopen("lct.in","r",stdin);freopen("lct.out","w",stdout);
	n=read(),m=read();for(int i=1;i<n;++i){int x(read()),y(read());insert(x,y);insert(y,x);}
	dfs1(1);dfs2(1,1);
	while(m--){
		scanf("%s",op);
		if(op[0]=='Q'){int x(read()),y(read());if(check(x,y))puts("Yes");else puts("No");}
		if(op[0]=='C'){int x(read()),y(read()),tmp(dep[x]>dep[y]?x:y);whi[++war]=tmp;update(id[tmp],1,1,n,1);}
		if(op[0]=='U'){int x(read());update(id[whi[x]],-1,1,n,1);}
	}
}