http://poj.org/problem?id=3321

利用DFS序的性质,注意更新的是左端点,

if (s[0] == 'C') update(l[x], has[x] ? -1 : 1), has[x] = !has[x];
else PI(query(l[x], r[x]));
/*1344ms,8904KB*/

const int mx = int(1e5) + 5;

vector<vector<int> > g(mx);
int step, l[mx], r[mx];

void dfs(int now, int fa)
{
    l[now] = ++step;
    int i;
    For(i, g[now].size()) if (g[now][i] != fa)
        dfs(g[now][i], now);
    r[now] = step;
}

int tree[mx];

void update(int pos, int val) {for (; pos <= step; pos += pos & -pos) tree[pos] += val;}
int sum(int pos) {int sum = 0; for (; pos; pos &= pos - 1) sum += tree[pos]; return sum;}
inline int query(int sta, int end) {return sum(end) - sum(sta - 1);}

bool has[mx];
char s[2];

int main()
{
    int n, i, a, b, q, x;
    SI(n);
    For(i, n - 1) SII(a, b), g[a].push_back(b), g[b].push_back(a);
    step = 0, dfs(1, 0);
    mem(has, 1);
    Forr(i, 1, n + 1) update(i, 1);
    SI(q);
    while (q--)
    {
        scanf("%s", s), SI(x);
        if (s[0] == 'C') update(l[x], has[x] ? -1 : 1), has[x] = !has[x];
        else PI(query(l[x], r[x]));
    }
    return 0;
}

Comments

comments powered by Disqus