|
|
|
|
|
#include <iostream>
|
|
|
#include <string.h>
|
|
|
#include <stdio.h>
|
|
|
#include <vector>
|
|
|
#include <map>
|
|
|
#include <queue>
|
|
|
#include <algorithm>
|
|
|
#include <math.h>
|
|
|
#include <cstdio>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 1e5 + 10, M = N << 1;
|
|
|
//邻接表
|
|
|
int e[M], h[N], idx, ne[M];
|
|
|
void add(int a, int b) {
|
|
|
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
// dfs序专用数据结构
|
|
|
int in[N], out[N], tot;
|
|
|
// dfs序模板
|
|
|
void dfs(int u, int fa) {
|
|
|
in[u] = ++tot; // dfs序中u节点进入 时间戳
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int j = e[i];
|
|
|
if (j == fa) continue; //不走回头路
|
|
|
dfs(j, u);
|
|
|
}
|
|
|
out[u] = tot; // dfs序中u节点退出 时间戳
|
|
|
}
|
|
|
|
|
|
//线段树结构体
|
|
|
struct Node {
|
|
|
int l, r;
|
|
|
int sum;
|
|
|
} tr[N << 2];
|
|
|
|
|
|
//向上更新父节点的子树苹果和
|
|
|
void pushup(int u) {
|
|
|
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
|
|
|
}
|
|
|
|
|
|
//构建线段树
|
|
|
void build(int u, int l, int r) {
|
|
|
tr[u] = {l, r};
|
|
|
if (l == r) {
|
|
|
tr[u].sum = 1; //最初的时候每个叶子节点上都是有苹果的
|
|
|
return;
|
|
|
}
|
|
|
int mid = (l + r) >> 1;
|
|
|
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
|
|
|
//向上更新父节点信息
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
//在以u为根的子树中修改x的值
|
|
|
void modify(int u, int x) {
|
|
|
if (tr[u].l == tr[u].r) {
|
|
|
tr[u].sum ^= 1; //异或就是将1变0，将0变1。
|
|
|
return;
|
|
|
}
|
|
|
int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
if (x <= mid)
|
|
|
modify(u << 1, x);
|
|
|
else
|
|
|
modify(u << 1 | 1, x);
|
|
|
pushup(u);
|
|
|
}
|
|
|
|
|
|
//查询区间值
|
|
|
int query(int u, int l, int r) {
|
|
|
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
|
|
|
int mid = (tr[u].l + tr[u].r) >> 1;
|
|
|
int ans;
|
|
|
if (r <= mid)
|
|
|
ans = query(u << 1, l, r);
|
|
|
else if (l > mid)
|
|
|
ans = query(u << 1 | 1, l, r);
|
|
|
else
|
|
|
ans = query(u << 1, l, r) + query(u << 1 | 1, l, r);
|
|
|
return ans;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int n, m;
|
|
|
scanf("%d", &n);
|
|
|
memset(h, -1, sizeof h);
|
|
|
for (int i = 1; i < n; i++) {
|
|
|
int a, b;
|
|
|
scanf("%d%d", &a, &b);
|
|
|
add(a, b), add(b, a);
|
|
|
}
|
|
|
//记录dfs序
|
|
|
dfs(1, 0);
|
|
|
|
|
|
//构建线段树
|
|
|
build(1, 1, n);
|
|
|
|
|
|
scanf("%d", &m);
|
|
|
while (m--) {
|
|
|
char op[2]; //注意：一般字符都需要用char数组读入，可以过滤掉空格和回车
|
|
|
int k;
|
|
|
scanf("%s%d", op, &k); //注意op按字符数组读入是不用&地址符的！
|
|
|
if (*op == 'C')
|
|
|
modify(1, in[k]); //原始第k个节点，对应线段树中第in[k]个节点
|
|
|
else
|
|
|
printf("%d\n", query(1, in[k], out[k])); //查询k这个点在in[k],out[k]区间内的sum和。
|
|
|
}
|
|
|
return 0;
|
|
|
} |
