【dfs+树状数组】苹果树

图论, 树状数组

传送门：CodeVS1228

思路：考虑到一棵树不怎么好搞，同时我们的查询都是基于子树的，于是可以用后序遍历为节点重新编号（后序遍历时子节点编号连续）

然后随便来个数据结构（树状数组多好）。

没了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define min(x,y) ((x)<(y)?(x):(y))
#define INF 0x3f3f3f3f
int n,m,x,y,tot,dfn[120000],Min[120000],head[120000],f[1200000],bit[240000];
char ch;
struct edge{int v,nxt;}e[240000];
void Insert(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void dfs(int x){
	dfn[x]=-1;
	for (int i=head[x];i;i=e[i].nxt){
		int v=e[i].v;
		if (!dfn[v]){
			dfs(v); Min[x]=min(Min[x],Min[v]);
		}
	}
	dfn[x]=++tot;
	if (Min[x]==INF) Min[x]=tot;
}
void add(int x,int y){
	for (int i=x;i<=n*2;i+=i&(-i)) bit[i]+=y;
}
int query(int x){
	int sum=0;
	for (int i=x;i>=1;i-=i&(-i)) sum+=bit[i];
	return sum;
}
		
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		Insert(x,y); Insert(y,x);
	}
	
	memset(Min,INF,sizeof Min);
	tot=0;
	dfs(1);
	
	for (int i=1;i<=n;i++){f[i]=1; add(dfn[i],f[i]);}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		for (ch=getchar();ch!='Q' && ch!='C';ch=getchar());
		scanf("%d",&x);
		if (ch=='Q')
			printf("%d\n",query(dfn[x])-query(Min[x]-1));
		else{
			f[x]=f[x]==1?-1:1; add(dfn[x],f[x]);
		}
	}
	
	return 0;
}