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
| #include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
const int N = 250005;
struct Edge{
int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
edge[++edgeNum] = (Edge){head[from], to};
head[from] = edgeNum;
}
int n, m, u, v, a[N] = {-1};
char s[2];
int st[N], ed[N], dfsClock;
void dfs(int x, int f){
st[x] = ed[x] = ++dfsClock;
a[st[x]] = a[st[f]] + 1;
for(int i = head[x]; i; i = edge[i].nxt){
if(edge[i].to == f) continue;
dfs(edge[i].to, x);
}
ed[x] = dfsClock;
}
struct segTree{
int l, r, sum, lazy;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
tr[id].sum = tr[lid].sum + tr[rid].sum;
}
inline void pushdown(int id){
if(tr[id].l == tr[id].r) return;
if(tr[id].lazy){
tr[lid].lazy += tr[id].lazy;
tr[lid].sum += len(lid) * tr[id].lazy;
tr[rid].lazy += tr[id].lazy;
tr[rid].sum += len(rid) * tr[id].lazy;
tr[id].lazy = 0;
}
}
void build(int id, int l, int r){
tr[id].l = l, tr[id].r = r;
tr[id].lazy = 0;
if(tr[id].l == tr[id].r){
tr[id].sum = a[l];
return;
}
build(lid, l, mid);
build(rid, mid+1, r);
pushup(id);
}
void add(int id, int l, int r, int val){
pushdown(id);
if(tr[id].l == l && tr[id].r == r){
tr[id].lazy += val;
tr[id].sum += len(id) * val;
return;
}
if(r <= mid) add(lid, l, r, val);
else if(l > mid) add(rid, l, r, val);
else add(lid, l, mid, val), add(rid, mid+1, r, val);
pushup(id);
}
int query(int id, int pos){
pushdown(id);
if(tr[id].l == tr[id].r) return tr[id].sum;
if(pos <= mid) return query(lid, pos);
else return query(rid, pos);
}
int main(){
read(n);
for(int i = 1; i < n; i++){
read(u, v);
addEdge(u, v);
addEdge(v, u);
}
dfs(1, 0);
build(1, 1, n);
read(m);
while(1){
scanf("%s", s);
if(s[0] == 'A'){
read(u, v);
if(u < v) swap(u, v);
add(1, st[u], ed[u], -1);
}
else{
read(u);
printf("%d\n", query(1, st[u]));
m--;
if(m == 0) break;
}
}
return 0;
}
|