「POI 2007」大都市【DFS 序】

Time Limit: 10 Sec Memory Limit: 192 MB

Description

在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员 Blue Mary 也开始骑着摩托车传递邮件了。不过,她经常回忆起以前在乡间漫步的情景。昔日,乡下有依次编号为 1..n1 .. nnn 个小村庄,某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄 11 (即比特堡)。对于每个村庄,它到比特堡的路径恰好只经过编号比自己的编号小的村庄。另外,对于所有道路而言,它们都不在除村庄以外的其他地点相遇。在这个欠发达的地方,从来没有过高架桥和地下铁道。随着时间的推移,越来越多的土路被改造成了公路。至今,Blue Mary 还清晰地记得最后一条土路被改造为公路的情景。现在,这里已经没有土路了,所有的路都成为了公路,而昔日的村庄已经变成了一个大都市。Blue Mary 想起了在改造期间她送信的经历。她从比特堡出发,需要去某个村庄,并且在两次送信经历的间隔期间,有某些土路被改造成了公路。

现在 Blue Mary 需要你的帮助:计算出她每次送信需要走过的土路数目。对于公路,她可以骑摩托车;而对于土路,她就只好推车了。

Input

11 行是一个数 nn (1n2500001 \leqslant n \leqslant 250000)。接下来 n1n-1 行,每行两个整数 a,ba, b (1a<bn1 \leqslant a < b \leqslant n)。
再下一行包含一个整数 mm (1 leqslantm2500001\ leqslant m \leqslant 250000),表示 Blue Mary 曾经在改造期间送过 mm 次信。再接下来 n+m1n+m-1 行,每行有两种格式的若干信息,表示按时间先后发生过的 n+m1n+m-1 次事件。

Output

mm 行,每行包含一个整数,表示对应的某次送信时经过的土路数目。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
1 2
1 3
1 4
4 5
4
W 5
A 1 4
W 5
A 4 5
W 5
W 2
A 1 2
A 1 3

Sample Output

1
2
3
4
2
1
0
1

Constraints

1n2500001 \leqslant n \leqslant 2500001m2500001 \leqslant m \leqslant 250000

Hint

样例解释

Solution

DFS\text {DFS} 序 + 树状数组:

  • 将树 DFS\text {DFS} 一遍, 得出 DFS\text {DFS} 序, 用树状数组维护 (差分)。
  • 将一个点进入是置为 11, 退出时置为 1-1
  • 每次修改公路就把这两个值都置为 00
  • 查询时把根节点多余的权值删去, 所以输出前缀和 1-1 即可。
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
#include <bits/stdc++.h>
using namespace std;

const int maxn = 250010;
int n, m, dfn, l[maxn], r[maxn], c[maxn * 2];
vector<int> G[maxn];

void dfs(int v, int p) {
l[v] = ++dfn;
for (int i = 0; i < G[v].size(); i++) {
if (G[v][i] != p) {
dfs(G[v][i], v);
}
}
r[v] = ++dfn;
}

void add(int x, int val) {
for (; x <= 2 * n; x += x & -x) {
c[x] += val;
}
}

int query(int x) {
int sum = 0;
for (; x >= 1; x -= x & -x) {
sum += c[x];
}
return sum;
}

int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0);
for (int i = 1; i <= n; i++) {
add(l[i], 1);
add(r[i], -1);
}
scanf("%d", &m);
m = n + m - 1;
while (m--) {
char op;
int a;
scanf("\n%c %d", &op, &a);
if (op == 'A') {
scanf("%d", &a);
add(l[a], -1);
add(r[a], 1);
} else {
printf("%d\n", query(l[a]) - 1);
}
}
return 0;
}