线段树+dfs序
给定一棵n个节点的树，m次查询，每次查询需要求出某个节点深度为h的所有子节点。
作为预处理，首先将树的所有节点按深度保存起来，每个深度的所有节点用一个线性结构保存，每个深度的节点相对顺序要和前序遍历一致。
然后从树的根节点进行dfs，对于每个节点记录两个信息，一个是dfs进入该节点的时间戳in[id]，另一个是dfs离开该节点的时间戳out[id]。
最后对于每次查询，求节点v在深度h的所有子节点，只需将深度为h并且dfs进入时间戳在in[v]和out[v]之间的所有节点都求出来即可。
Step 1：
如下图，可以看到，由于普通的树并不具有区间的性质，所以在考虑使用线段树作为解题思路时，需要对给定的数据进行转化，首先对这棵树进行一次dfs遍历，记录dfs序下每个点访问起始时间与结束时间，记录起始时间是前序遍历，结束时间是后序遍历，同时对这课树进行重标号。
Step 2：
如下图，DFS之后，那么树的每个节点就具有了区间的性质。
那么此时，每个节点对应了一个区间，而且可以看到，每个节点对应的区间正好“管辖”了它子树所有节点的区间，那么对点或子树的操作就转化为了对区间的操作。
例题一：
POJ-3321 Apple Tree
There is an apple tree outside of kaka‘s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.
The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won‘t grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.
The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?
Input
The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
"C x" which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
"Q x" which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning
Output
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
题目大意：
一棵树上长了苹果，每一个树枝节点上有长苹果和不长苹果两种状态，两种操作，一种操作能够改变树枝上苹果的状态，另一种操作询问某一树枝节点一下的所有的苹果有多少。操作C：如果有苹果，则经过C操作变成没有，如果没有苹果，经过C操作变成有。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 const int maxn=100010;
7 struct node{
8 int to;
9 int nex;
10 }e[maxn<<2];
11 int head[maxn<<2],v[maxn<<2],u[maxn<<2];
12 int vis[maxn<<2],cnt,num;
13 struct tree{
14 int l;
15 int r;
16 int sum;
17 }tree[maxn<<2];
18 void init()
19 {
20 memset(vis,0,sizeof(vis));
21 memset(head,-1,sizeof(head));
22 cnt=0;
23 }
24 void dfs(int x)
25 {
26 ++num;
27 v[x]=num;
28 vis[x]=1;
29 for(int i=head[x];i!=-1;i=e[i].nex)
30 {
31 int t=e[i].to;
32 if(vis[t]==1)
33 continue;
34 dfs(t);
35 }
36 u[x]=num;
37 }
38 void add(int x,int y)
39 {
40 e[cnt].to=y;
41 e[cnt].nex=head[x];
42 head[x]=cnt++;
43 }
44 void pushup(int cur)
45 {
46 tree[cur].sum=tree[cur<<1].sum+tree[cur<<1|1].sum;
47 }
48 void build(int l,int r,int cur)
49 {
50 tree[cur].l=l;
51 tree[cur].r=r;
52 if(l==r)
53 {
54 tree[cur].sum=1;
55 return;
56 }
57 int mid=(l+r)/2;
58 build(l,mid,cur<<1);
59 build(mid+1,r,cur<<1|1);
60 pushup(cur);
61 }
62 void update(int val,int cur)
63 {
64 if(tree[cur].l==tree[cur].r)
65 {
66 if(tree[cur].sum==0)
67 {
68 tree[cur].sum=1;
69 return;
70 }
71 else
72 {
73 tree[cur].sum=0;
74 return;
75 }
76 }
77 int mid=(tree[cur].l+tree[cur].r)/2;
78 if(val<=mid)
79 update(val,cur<<1);
80 if(val>=mid+1)
81 update(val,cur<<1|1);
82 pushup(cur);
83 }
84 int query(int pl,int pr,int cur)
85 {
86 if(pl<=tree[cur].l&&tree[cur].r<=pr)
87 {
88 return tree[cur].sum;
89 }
90 int ans=0;
91 int mid=(tree[cur].l+tree[cur].r)/2;
92 if(pl<=mid)
93 ans+=query(pl,pr,cur<<1);
94 if(pr>=mid+1)
95 ans+=query(pl,pr,cur<<1|1);
96 return ans;
97 }
98 int main()
99 {
100 int n,m;
101 int a,b;
102 while(~scanf("%d",&n)&&n)
103 {
104 init();
105 num=0;
106 for(int i=1;i<=n-1;i++)
107 {
108 scanf("%d%d",&a,&b);
109 add(a,b);
110 }
111 dfs(1);
112 char s[5];
113 build(1,n,1);
114 scanf("%d",&m);
115 while(m--)
116 {
117 scanf("%s%d",s,&a);
118 if(s[0]==‘C‘)
119 {
120 update(v[a],1);
121 }
122 if(s[0]==‘Q‘)
123 {
124 printf("%d\n",query(v[a],u[a],1));
125 }
126 }
127 }
128 }
HDU-3974 Assign the task
The company usually assigns some tasks to some employees to finish.When a task is assigned to someone,He/She will assigned it to all his/her subordinates.In other words,the person and all his/her subordinates received a task in the same time. Furthermore,whenever a employee received a task,he/she will stop the current task(if he/she has) and start the new one.
Write a program that will help in figuring out some employee’s current task after the company assign some tasks to some employee.
InputThe first line contains a single positive integer T( T <= 10 ), indicates the number of test cases.
For each test case:
The first line contains an integer N (N ≤ 50,000) , which is the number of the employees.
The following N - 1 lines each contain two integers u and v, which means the employee v is the immediate boss of employee u(1<=u,v<=N).
The next line contains an integer M (M ≤ 50,000).
The following M lines each contain a message which is either
"C x" which means an inquiry for the current task of employee x
or
"T x y"which means the company assign task y to employee x.
(1<=x<=N,0<=y<=10^9)OutputFor each test case, print the test case number (beginning with 1) in the first line and then for every inquiry, output the correspond answer per line.Sample Input
1
5
4 3
3 2
1 3
5 2
5
C 3
T 2 1
C 3
T 3 2
C 3
Sample Output
Case #1:
-1
1
2
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=50010; 7 struct node{ 8 int to; 9 int nex; 10 }e[maxn<<2]; 11 int head[maxn<<2],v[maxn<<2],u[maxn<<2]; 12 int vis[maxn<<2],cnt,num,in[maxn<<2]; 13 struct tree{ 14 int l; 15 int r; 16 int sum; 17 int laz; 18 }tree[maxn<<3]; 19 void init() 20 { 21 memset(tree,0,sizeof(tree)); 22 memset(e,0,sizeof(e)); 23 memset(v,0,sizeof(v)); 24 memset(u,0,sizeof(u)); 25 memset(in,0,sizeof(in)); 26 memset(vis,0,sizeof(vis)); 27 memset(head,-1,sizeof(head)); 28 cnt=0; 29 } 30 void dfs(int x) 31 { 32 ++num; 33 v[x]=num; 34 vis[x]=1; 35 for(int i=head[x];i!=-1;i=e[i].nex) 36 { 37 int t=e[i].to; 38 if(vis[t]==1) 39 continue; 40 dfs(t); 41 } 42 u[x]=num; 43 } 44 void add(int x,int y) 45 { 46 e[cnt].to=y; 47 e[cnt].nex=head[x]; 48 head[x]=cnt++; 49 } 50 void pushdown(int cur) 51 { 52 if(tree[cur].laz!=0) 53 { 54 tree[cur<<1].laz=tree[cur<<1|1].laz=tree[cur].laz; 55 tree[cur<<1].sum=tree[cur<<1|1].sum=tree[cur].laz; 56 tree[cur].laz=0; 57 } 58 return; 59 } 60 61 void build(int l,int r,int cur) 62 { 63 tree[cur].l=l; 64 tree[cur].r=r; 65 tree[cur].laz=0; 66 tree[cur].sum=0; 67 if(l==r) 68 { 69 return; 70 } 71 int mid=(l+r)/2; 72 build(l,mid,cur<<1); 73 build(mid+1,r,cur<<1|1); 74 } 75 void update(int pl,int pr,int num,int cur) 76 { 77 if(pl<=tree[cur].l&&tree[cur].r<=pr) 78 { 79 tree[cur].laz=num; 80 tree[cur].sum=num; 81 return; 82 } 83 pushdown(cur); 84 int mid=(tree[cur].l+tree[cur].r)/2; 85 if(pl<=mid) 86 update(pl,pr,num,cur<<1); 87 if(pr>=mid+1) 88 update(pl,pr,num,cur<<1|1); 89 } 90 int query(int pl,int pr,int cur)//一定要注意query中不能缺少pushdown 91 { 92 if(pl<=tree[cur].l&&tree[cur].r<=pr) 93 { 94 return tree[cur].sum; 95 } 96 //int ans=0; 97 pushdown(cur); 98 int mid=(tree[cur].l+tree[cur].r)/2; 99 if(pl<=mid) 100 return query(pl,pr,cur<<1); 101 if(pr>=mid+1) 102 return query(pl,pr,cur<<1|1); 103 } 104 int main() 105 { 106 int T; 107 int n,m; 108 int a,b; 109 cin>>T; 110 int id=1; 111 while(T--) 112 { 113 num=0; 114 init(); 115 scanf("%d",&n); 116 for(int i=1;i<=n-1;i++) 117 { 118 scanf("%d%d",&a,&b); 119 add(b,a); 120 in[a]++; 121 } 122 for(int i=1;i<=n;i++) 123 { 124 if(in[i]==0) 125 { 126 dfs(i); 127 break; 128 } 129 } 130 char s[5]; 131 build(1,n,1);printf("Case #%d:\n",id++); 132 scanf("%d",&m); 133 while(m--) 134 { 135 scanf("%s",s); 136 if(s[0]==‘C‘) 137 { 138 scanf("%d",&a); 139 int ans=query(v[a],u[a],1); 140 if(ans==0) 141 printf("-1\n"); 142 else 143 printf("%d\n",ans); 144 } 145 if(s[0]==‘T‘) 146 { 147 scanf("%d%d",&a,&b); 148 update(v[a],u[a],b,1); 149 } 150 } 151 } 152 }
参考博客：