POJ3321 Apple Tree
题意：给定一棵树，有两种操作：1、把某个节点上的数^1(若是1改为0，是0改为1) 2、查询以某个节点为根节点的子树中1的个数
在一棵树上进行单点修改和查询，只要进行一遍dfs，记录每个点的dfs序即可把问题转化到链上用线段树进行维护
更改和模板一样，查询时以每棵子树遍历时第一个节点的dfs序和最后一个节点的边界作为查询区间（每颗子树中节点的DFS序是连续的）
#include <stdio.h>
#include <iostream>
using namespace std;
inline void read (int &x) {
char ch = getchar(); x = 0;
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}
void print (int x) {
if (x > 9) print (x / 10);
putchar (x % 10 + 48);
}
const int N = 1e6 + 10;
int n, cnt, tot, m, pos, ql, qr, s[N << 2], num[N], l[N], r[N], nxt[N << 1], to[N << 1], h[N];
inline void add (int u, int v) {
to[++tot] = v, nxt[tot] = h[u], h[u] = tot;
}
void dfs (int u, int la) {
num[u] = l[u] = ++ cnt;
for (int i = h[u]; i; i = nxt[i]) if (to[i] != la) dfs (to[i], u);
r[u] = cnt; //l、r记录每颗子树中最小和最大的dfs序
}
#define ls p << 1
#define rs p << 1 | 1
void build (int p, int l, int r) {
if (l == r) {s[p] = 1; return;}
int mid (l + r >> 1);
build (ls, l, mid), build (rs, mid + 1, r);
s[p] = s[ls] + s[rs];
}
void change (int p, int l, int r) {
if (l == r) {s[p] ^= 1; return;} //把0改为1，把1改为0，相当于当前数字^1
int mid (l + r >> 1);
pos <= mid ? change (ls, l, mid) : change (rs, mid + 1, r);
s[p] = s[ls] + s[rs];
}
int query (int p, int l, int r) {
if (ql <= l && qr >= r) return s[p];
int mid (l + r >> 1), t (0);
if (ql <= mid) t += query (ls, l, mid);
if (qr > mid) t += query (rs, mid + 1, r);
return t;
}
int main() {
read (n);
for (int i = 1, u, v; i < n; ++i)
read (u), read (v), add (u, v), add (v, u);
dfs (1, 0); build (1, 1, n);
read (m);
for (int i = 1; i <= m; ++i) {
char ch = getchar(); getchar();
if (ch == 'C') read (pos), pos = num[pos], change (1, 1, n);
else read (pos), ql = l[pos], qr = r[pos], print (query (1, 1, n)), puts ("");
}
return 0;
}