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
| #include<bits/stdc++.h>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define for_edge(i, x) for(RG int i=head[x];i;i=e[i].next)
#define clear(x, y) memset(x, y, sizeof(x));
using namespace std;
inline int read()
{
int data=0, w=1;
char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') w=-1, ch=getchar();
while(ch>='0'&&ch<='9') data=(data<<3)+(data<<1)+(ch^48), ch=getchar();
return data*w;
}
const int maxn(1e5+10);
struct edge { int next, to; } e[maxn << 1];
int head[maxn], e_num, n, m;
inline void add_edge(int from, int to) { e[++e_num]=(edge){head[from], to}; head[from]=e_num; }
int fa[maxn], size[maxn], heavy[maxn], val[maxn];
void dfs(int x)
{
size[x]=1;
int _max=0;
for_edge(i, x)
{
int to=e[i].to;
if(to==fa[x]) continue;
fa[to]=x; dfs(to);
size[x]+=size[to];
if(_max < size[to]) _max=size[to], heavy[x]=to;
}
}
int pos[maxn], cnt_pos[maxn], belong[maxn], cnt_node;
void dfs(int x, int chain)
{
belong[x]=chain;
pos[x]=++cnt_node;
cnt_pos[cnt_node]=x;
int k=heavy[x];
if(!k) return;
dfs(k, chain);
for_edge(i, x)
{
int to=e[i].to;
if(to==fa[x] || to==k) continue;
dfs(to, to);
}
}
int sum[maxn << 2];
#define son(i) ((root<<1)|i)
inline void build(int root=1, int l=1, int r=cnt_node)
{
if(l==r) { sum[root]=val[cnt_pos[l]]; return; }
int mid(l+r>>1); build(son(0), l, mid); build(son(1), mid+1, r);
sum[root]=sum[son(0)]+sum[son(1)];
}
inline void update(int id, int root=1, int l=1, int r=cnt_node)
{
if(l==r) { sum[root]=0; return; }
int mid(l+r>>1);
if(id<=mid) update(id, son(0), l, mid);
else update(id, son(1), mid+1, r);
sum[root]=sum[son(0)]+sum[son(1)];
}
inline int query(int ql, int qr, int root=1, int l=1, int r=cnt_node)
{
if(r<ql || l>qr) return 0;
if(ql<=l && r<=qr) return sum[root];
int mid(l+r>>1);
return query(ql, qr, son(0), l, mid)+query(ql, qr, son(1), mid+1, r);
}
inline int query_chain(int a)
{
int ans=0;
while(belong[a]!=1)
{
ans+=query(pos[belong[a]], pos[a]);
a=fa[belong[a]];
}
ans+=query(1, pos[a]);
return ans;
}
char s[3];
int a, b;
int main()
{
n=read();
for(RG int i=1;i<n;i++) a=read(), b=read(), add_edge(a, b), add_edge(b, a), val[i+1]=1;
dfs(1); dfs(1, 1); build();
m=read();
for(RG int i=1;i<n+m;i++)
{
scanf("%s", s);
a=read();
if(s[0]=='W') printf("%d\n", query_chain(a));
else b=read(), update(pos[b]);
}
return 0;
}
|