#include <cstdio>
#include <cassert>
#include <utility>
#include <vector>

using namespace std;

struct tree_array {
    const static int size_max = 100010;
    int n, num[size_max];
    void add(int pos, int key) {
        for (; pos <= n; pos += low_bit(pos))
            num[pos] += key;
    }
    int get_sum(int pos) {
        int res = 0;
        for (; pos > 0; pos -= low_bit(pos))
            res += num[pos];
        return res;
    }
    int low_bit(int x) {
        return x & (-x);
    }
};

int n, m, apple[100001], num;
vector<int> network[100001];
pair<int, int> pos[100001];
bool visited[100001];
tree_array tree;

void build_tree(int);

int main() {
    scanf("%d", &n);
    assert(n >= 1 && n <= 100000);////
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        assert(u >= 1 && u <= n);////
        assert(v >= 1 && v <= n);////
        network[u].push_back(v);
        network[v].push_back(u);
    }
    build_tree(1);
    tree.n = n;
    for (int i = 1; i <= n; ++i) {
        tree.add(i, apple[i] = 1);
        assert(visited[i]);////
    }
    scanf("%d", &m);
    for (int i = 0, v; i < m; ++i) {
        char buf[10];
        scanf("%s%d", buf, &v);
        assert(v >= 1 && v <= n);////
        assert(buf[0] == 'C' || buf[0] == 'Q');////
        if (buf[0] == 'C') {
            assert(apple[v] == 0 || apple[v] == 1);////
            tree.add(v, ((apple[v] ^= 1) == 0) ? -1 : 1);
        } else if (buf[0] == 'Q') {
            int tmp = tree.get_sum(pos[v].second) - tree.get_sum(pos[v].first - 1);
            assert(tmp >= 0);////
            printf("%d\n", tmp);
        }
    }
    return 0;
}

void build_tree(int cur) {
    assert(!visited[cur]);////
    visited[cur] = true;
    pos[cur].first = ++num;
    for (int i = 0; i < network[cur].size(); ++i)
        if (!visited[network[cur][i]])
            build_tree(network[cur][i]);
    //for (vector<int>::iterator i = network[cur].begin(); i != network[cur].end(); ++i)
    //    if (!visited[*i])
    //        build_tree(*i);
    pos[cur].second = num;
}

• Re:这个题目使用vector和树状数组WA了一下午了……怎么都找不出错误……谁能帮忙看看，或者给点数据……不胜感激…… (15) Dumbear 2009-05-26 17:51:03