记录编号	466751	评测结果	EEEEEEEEEE
题目名称	艺术	最终得分	0
用户昵称	BaDBoY	是否通过	未通过
代码语言	C++	运行时间	0.755 s
提交时间	2017-10-29 16:30:27	内存使用	28.36 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define mid (l+r>>1)
char buf[300005*30], *ptr=buf-1;
inline int read(){
    register int x=0,f=1,c=*++ptr;
    while (c<48) c=='-'&&(f=-1),c=*++ptr;
    while (c>47) x=x*10+c-48,c=*++ptr;
    return x * f;
}
int n,m,war,whi[300005],tot,r[300005];
struct EDGE{int to,next;} c[600005];
void add(int x,int y) {
	c[++tot]=(EDGE){y,r[x]};
	r[x]=tot;
}
int fa[300005],son[300005],size[300005],dep[300005];
inline void dfs1(int u){
	size[u]=1;son[u]=0;
	for(int i=r[u]; ~i; i=c[i].next){
		int to=c[i].to;
		if(to==fa[u])continue;
		fa[to]=u;dep[to]=dep[u]+1;dfs1(to);
		size[u]+=size[to];if(size[to]>size[son[u]])son[u]=to;
	}
}
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(int i=r[u]; ~i; i=c[i].next){int to=c[i].to; if(to==fa[u]||to==son[u]) continue; dfs2(to,to);}
}
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;}
	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 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[5];
int Main(){
	freopen("lct.in","r",stdin);
	freopen("lct.out","w",stdout);
	fread(buf,1,sizeof(buf),stdin);
	memset(r,0xff,sizeof(r));
	n=read(),m=read();for(int i=1;i<n;++i){int x=read(),y=read();add(x,y);add(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);}
	}
}
int hehe=Main();
int main(){;}