学步园

题意：一棵苹果树有n个结点，开始时每个结点有一个苹果，这n个结点由m条枝连起来，现执行以下两种操作，C x：如果结点x原来有苹果，则把它摘掉，如果没有，则长出1个苹果。Q x：询问以x为根的树的苹果共几个？

题目链接：http://poj.org/problem?id=3321

——>>求一棵子树的和，转化为求一个连续区间的和。用线段树进行维护，时间复杂度为O(max(N, M*log(N)))。。

#include <cstdio>
#include <cstring>

using namespace std;

#define lc (o<<1)
#define rc ((o<<1)|1)

const int maxn = 100000 + 10;

int l[maxn], r[maxn], dfs_clock;
int hed[maxn], v[maxn<<1], nxt[maxn<<1], ecnt;
int sum[maxn<<2];

void init() {
    memset(hed, -1, sizeof(hed));
    ecnt = 0;
    dfs_clock = 1;
}

void add_edge(int uu, int vv) {
    v[ecnt] = vv;
    nxt[ecnt] = hed[uu];
    hed[uu] = ecnt++;
}

void dfs(int x, int f) {
    l[x] = dfs_clock;
    for(int e = hed[x]; e != -1; e = nxt[e]) {
        int vv = v[e];
        if(vv != f) dfs(vv, x);
    }
    r[x] = dfs_clock++;
}

void build(int o, int L, int R) {
    if(L == R) {
        sum[o] = 1;
        return;
    }
    int M = (L + R) >> 1;
    build(lc, L, M);
    build(rc, M+1, R);
    sum[o] = sum[lc] + sum[rc];
}

void update(int o, int L, int R, int x) {
    if(L == R) {
        sum[o] ^= 1;
        return;
    }
    int M = (L + R) >> 1;
    if(x <= M) update(lc, L, M, x);
    else update(rc, M+1, R, x);
    sum[o] = sum[lc] + sum[rc];
}

int query(int o, int L, int R, int ql, int qr) {
    if(ql <= L && R <= qr) return sum[o];
    int M = (L + R) >> 1;
    int ans = 0;
    if(ql <= M) ans += query(lc, L, M, ql, qr);
    if(qr > M) ans += query(rc, M+1, R, ql, qr);
    return ans;
}

int main()
{
    char op;
    int N, a, b, M, x;
    while(scanf("%d", &N) == 1) {
        init();
        for(int i = 1; i < N; i++) {
            scanf("%d%d", &a, &b);
            add_edge(a, b);
            add_edge(b, a);
        }
        dfs(1, -1);
        build(1, 1, N);
        scanf("%d", &M);
        while(M--) {
            getchar();
            scanf("%c%d", &op, &x);
            if(op == 'C') update(1, 1, N, r[x]);
            else printf("%d\n", query(1, 1, N, l[x], r[x]));
        }
    }
    return 0;
}