python/TangDou/AcWing/POJ3321.cpp

#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;
}