题面

大秦 为你打开 题目传送门

题目翻译

给定一个包含N个结点的苹果树，结点从1到N编号，树根为1。

苹果会长在某些结点上，但是两个苹果不会同时长在一个结点上。

随着时间的推移，苹果会被摘走，或者某些结点又长出新苹果。

现在我们想知道在某个时刻某个子树中有多少苹果。

思路

首先不难想到用线段树（当然也可以树状数组），在树上的线段树问题一般都得用 Dfs 序或者树链剖分把他们化作区间上的问题解决。而这道题特别简单，没有大的需求用树链剖分，这里使用Dfs序，所谓Dfs序，就是记录他第一次被访问，和最后一次被访问的位置，这样就转化成了区间，而且这样这个区间可以包含他的整个子树。

代码

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
114
115
116
117
118
119
120
#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
const int M = 200010;

struct Node {
    int L, R;
    int num;
    Node() {}
    Node(int L, int R, int num) : L(L), R(R), num(num) {}
    Node operator + (const Node &b) const {
        return Node(min(L, b.L), max(R, b.R), num + b.num);
    }
};
class SegTree {
    private :
        Node node[N << 2];
    public :
        void Build(int p, int L, int R) {
            node[p].L = L , node[p].R = R;
            if(L == R) {
                node[p].num = 1;
                return ;
            }
            int mid = L + R >> 1;
            Build(p << 1, L, mid);
            Build(p << 1 | 1, mid + 1, R);
            node[p] = node[p << 1] + node[p << 1 | 1];
        }
        void Modify(int p, int x) {
            if(node[p].L == node[p].R) {
                node[p].num ^= 1;
                return ;
            }
            int mid = node[p].L + node[p].R >> 1;
            if(x <= mid) Modify(p << 1, x);
            else Modify(p << 1 | 1, x);
            node[p] = node[p << 1] + node[p << 1 | 1];
        }
        int Query(int p, int L, int R) {
            if(L <= node[p].L && node[p].R <= R) {
                return node[p].num;
            }
            int mid = node[p].L + node[p].R >> 1;
            int ans = 0;
            if(L <= mid) ans += Query(p << 1, L, R);
            if(R > mid) ans += Query(p << 1 | 1, L, R);
            return ans;
        }
};

class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, Q;
Graph G;

SegTree tree;
int in[N], ot[N], cntd;

void Input() {
    scanf("%d", &n);
    int u, v;
    for(int i = 1; i < n; i++) {
        scanf("%d%d", &u, &v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
    scanf("%d", &Q);
}

void Dfs(int u, int fa) {
    in[u] = ++cntd;
    for(int i = G.head(u); i ; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa) continue;
        Dfs(v, u);
    }
    ot[u] = cntd;
}

void Work() {
    Dfs(1, 0);
    tree.Build(1, 1, n);
    char op;
    int x;
    while(Q--) {
        scanf(" %c%d", &op, &x);
        // cout << op << ' ' << x << endl;
        if(op == 'Q') {
            printf("%d\n", tree.Query(1, in[x], ot[x]));
        }
        else {
            tree.Modify(1, in[x]);
        }
    }
}

int main() {
    Input();
    Work();
    return 0；
}