1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
#include<algorithm>
#include<cstring>
using namespace std;
namespace io{
#define re register
#define ll long long
#define inf 0x3f3f3f3f
#define il inline
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)
il void (ll &x){
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
il void read(int &x){
x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
}using namespace io;
#define N 300005
#define ls p<<1
#define rs p<<1|1
int n,m,en,cnt,tot;
int front[N],fa[N],dep[N],size[N],top[N],id[N],son[N],war[N],tree[N<<2];
struct edge{
int v,next;
}e[N<<1];
il void addedge(int u,int v){
en++;
e[en].v=v;
e[en].next=front[u];
front[u]=en;
}
void dfs1(int u,int f){
dep[u]=dep[f]+1;
fa[u]=f;
size[u]=1;
int maxson=-1;
for(re int i=front[u];i;i=e[i].next){
int v=e[i].v;
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if(maxson<size[v]) maxson=size[v],son[u]=v;
}
}
void dfs2(int u,int topf){
id[u]=++cnt;
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(re int i=front[u];i;i=e[i].next){
int v=e[i].v;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
il void up(int p){
tree[p]=tree[ls]+tree[rs];
}
void add(int p,int l,int r,int pos,int val){
if(l==r){
tree[p]=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) add(ls,l,mid,pos,val);
else add(rs,mid+1,r,pos,val);
up(p);
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tree[p];
}
int mid=(l+r)>>1,res=0;
if(ql<=mid) res+=query(ls,l,mid,ql,qr);
if(qr>mid) res+=query(rs,mid+1,r,ql,qr);
return res;
}
il bool qrange(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res+=query(1,1,n,id[x],id[y])-query(1,1,n,id[x],id[x]);
return res==0;
}
int main(){
int u,v,x;
char ch;
in2(n,m);
for(re int i=1;i<=n-1;i++) in2(u,v),addedge(u,v),addedge(v,u);
dfs1(1,0);
dfs2(1,0);
while(m--){
scanf(" %c",&ch);
if(ch=='Q'){
in2(u,v);
if(qrange(u,v)) puts("Yes");
else puts("No");
}
else if(ch=='C'){
in2(u,v);
if(dep[u]>dep[v]) swap(u,v);
war[++tot]=v;
add(1,1,n,id[v],1);
}
else{
read(x);
add(1,1,n,id[war[x]],0);
}
}
return 0;
}
|
近期评论