### Brief description:

給定一棵樹，每個結點有 0/1 兩種狀態，要求動態維護以下操作。（初始全 1 .. .

- C x: 將 x 點的狀態取反。
- Q x: 詢問以 x 結點為根子樹中，1 的個數。

### Analysis:

… 略）。。（ DFS 序列 + (線段樹 or 樹狀數組)。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1169124

const int N = 100009, M = 2 * N; int L[N], R[N], cnt; // Vertex .. . int hd[N], nxt[M], a[M], b[M]; // Adjacent List .. . int C[4*N]; // Interval Tree int n; #define root 1, 1, n #define lx (x<<1) #define rx (lx|1) #define m ((l+r)>>1) #define lc lx, l, m, a, b #define rc rx, m+1, r, a, b #define pos a #define delta b void Modify(int x, int l, int r, int pos, int delta){ C[x] += delta; if (l < r){ if (pos <= m) Modify(lc); else Modify(rc); } } #undef pos int Sum(int x, int l, int r, int a, int b){ if (a <= l && r <= b) return C[x]; else return (a <= m ? Sum(lc) : 0) + (m < b ? Sum(rc) : 0); } #define v b[i] inline void dfs(int u = 0){ L[u] = ++cnt; for (int i=hd[u];i;i=nxt[i]) if (!L[v]){ dfs(v); } R[u] = cnt; } int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); #endif FOR_C(i, 2, _RD(n) << 1){ RD(a[i], b[i]), --a[i], --b[i], a[i|1] = b[i], b[i|1] = a[i]; nxt[i] = hd[a[i]], hd[a[i]] = i; ++i; nxt[i] = hd[a[i]], hd[a[i]] = i; } dfs(); REP_1(i, n) Modify(root, i, 1); char cmd; int pos; DO_C(RD()){ RC(cmd); --_RD(pos); if (cmd == 'C'){ Modify(root, L[pos], Sum(root, L[pos], L[pos]) ? -1 : 1); } else{ OT(Sum(root, L[pos], R[pos])); } } }

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1169082

const int N = 100009, M = 2 * N; int L[N], R[N], cnt; // Vertex .. . int hd[N], nxt[M], a[M], b[M]; // Adjacent List .. . int C[N]; // Interval Tree int n; void Modify(int x, int d){ while (x <= n) C[x] += d, x += low_bit(x); } int Sum(int x){ int res = 0; while (x) res += C[x], x ^= low_bit(x); return res; } int Sum(int l, int r){ return Sum(r) - Sum(l-1); } int Single(int x){ int res = C[x], p = low_bit(x); --x; while (x && low_bit(x) < p){ res -= C[x]; x ^= low_bit(x); } return res; } #define v b[i] inline void dfs(int u = 0){ L[u] = ++cnt; for (int i=hd[u];i;i=nxt[i]) if (!L[v]){ dfs(v); } R[u] = cnt; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif FOR_C(i, 2, _RD(n) << 1){ RD(a[i], b[i]), --a[i], --b[i], a[i|1] = b[i], b[i|1] = a[i]; nxt[i] = hd[a[i]], hd[a[i]] = i; ++i; nxt[i] = hd[a[i]], hd[a[i]] = i; } dfs(); REP_1(i, n) Modify(i, 1); char cmd; int pos; DO_C(RD()){ RC(cmd); --_RD(pos); if (cmd == 'C'){ Modify(L[pos], Single(L[pos]) ? -1 : 1); } else{ OT(Sum(L[pos], R[pos])); } } }