111 lines
2.7 KiB
C++
111 lines
2.7 KiB
C++
|
||
#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;
|
||
} |