POJ - 3321 Apple Tree

原题链接

思路

答案不好直接维护，所以，我们可以采用 DFS 序来解决这一问题。

设 \(l_u\) 是以 \(u\) 为根的子树中最小的时间戳，\(r_u\) 是以 \(u\) 为根的子树中最大的时间戳。那么所有 \(u\) 的祖先构成的集合 \(fa_u\)，对于任意元素 \(x\in fa_u\)，都有 \([l_u,r_u]\subseteq [l_x,r_x]\)。

知道了这个性质以后，就可以维护了。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010,M = 2 * N;
int n,m;
int h[N],e[M],ne[M],idx;
int d[N];
int c[N];
int l[N],r[N],timestamp;
void add (int a,int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}
void dfs (int u,int fa) {
	l[u] = ++timestamp;
	for (int i = h[u];~i;i = ne[i]) {
		int j = e[i];
		if (j == fa) continue;
		dfs (j,u);
	}
	r[u] = timestamp;
}
int lowbit (int x) {
	return x & -x;
}
void modify (int x,int d) {
	for (int i = x;i <= n;i += lowbit (i)) c[i] += d;
}
int query (int x) {
	int ans = 0;
	for (int i = x;i;i -= lowbit (i)) ans += c[i];
	return ans;
}
int main () {
	memset (h,-1,sizeof (h));
	scanf ("%d",&n);
	for (int i = 1;i <= n - 1;i++) {
		int a,b;
		scanf ("%d%d",&a,&b);
		add (a,b),add (b,a);
	}
	dfs (1,-1);
	for (int i = 1;i <= n;i++) modify (i,1),d[i] = 1;
	scanf ("%d",&m);
	while (m--) {
		char op[2];
		int x;
		scanf ("%s%d",op,&x);
		if (*op == 'C') {
			if (d[x]) modify (l[x],-1),d[x] = 0;
			else modify (l[x],1),d[x] = 1;
		}
		else printf ("%d\n",query (r[x]) - query (l[x] - 1));
	}
    return 0;
}