线段树+dfs序（Apple Tree ）（Assign the task ）

风流不在谈锋胜，袖手无言味最长。这篇文章主要讲述线段树+dfs序（Apple Tree ）（Assign the task ）相关的知识，希望能为你提供帮助。
线段树+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
For every inquiry, output the correspond answer per line.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{ 8int to; 9int 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{ 14int l; 15int r; 16int sum; 17 }tree[maxn< < 2]; 18 void init() 19 { 20memset(vis,0,sizeof(vis)); 21memset(head,-1,sizeof(head)); 22cnt=0; 23 } 24 void dfs(int x) 25 { 26++num; 27v[x]=num; 28vis[x]=1; 29for(int i=head[x]; i!=-1; i=e[i].nex) 30{ 31int t=e[i].to; 32if(vis[t]==1) 33continue; 34dfs(t); 35} 36u[x]=num; 37 } 38 void add(int x,int y) 39 { 40e[cnt].to=y; 41e[cnt].nex=head[x]; 42head[x]=cnt++; 43 } 44 void pushup(int cur) 45 { 46tree[cur].sum=tree[cur< < 1].sum+tree[cur< < 1|1].sum; 47 } 48 void build(int l,int r,int cur) 49 { 50tree[cur].l=l; 51tree[cur].r=r; 52if(l==r) 53{ 54tree[cur].sum=1; 55return; 56} 57int mid=(l+r)/2; 58build(l,mid,cur< < 1); 59build(mid+1,r,cur< < 1|1); 60pushup(cur); 61 } 62 void update(int val,int cur) 63 { 64if(tree[cur].l==tree[cur].r) 65{ 66if(tree[cur].sum==0) 67{ 68tree[cur].sum=1; 69return; 70} 71else 72{ 73tree[cur].sum=0; 74return; 75} 76} 77int mid=(tree[cur].l+tree[cur].r)/2; 78if(val< =mid) 79update(val,cur< < 1); 80if(val> =mid+1) 81update(val,cur< < 1|1); 82pushup(cur); 83 } 84 int query(int pl,int pr,int cur) 85 { 86if(pl< =tree[cur].l& & tree[cur].r< =pr) 87{ 88return tree[cur].sum; 89} 90int ans=0; 91int mid=(tree[cur].l+tree[cur].r)/2; 92if(pl< =mid) 93ans+=query(pl,pr,cur< < 1); 94if(pr> =mid+1) 95ans+=query(pl,pr,cur< < 1|1); 96return ans; 97 } 98 int main() 99 { 100int n,m; 101int a,b; 102while(~scanf("%d",& n)& & n) 103{ 104init(); 105num=0; 106for(int i=1; i< =n-1; i++) 107{ 108scanf("%d%d",& a,& b); 109add(a,b); 110} 111dfs(1); 112char s[5]; 113build(1,n,1); 114scanf("%d",& m); 115while(m--) 116{ 117scanf("%s%d",s,& a); 118if(s[0]==‘C‘) 119{ 120update(v[a],1); 121} 122if(s[0]==‘Q‘) 123{ 124printf("%d ",query(v[a],u[a],1)); 125} 126} 127} 128 }

HDU-3974 Assign the task
There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate boss of someone,that person is your subordinate, and all his subordinates are your subordinates as well. If you are nobody‘s boss, then you have no subordinates,the employee who has no immediate boss is the leader of whole company.So it means the N employees form a tree.

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

【线段树+dfs序（Apple Tree ）（Assign the task ）】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{ 8int to; 9int 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{ 14int l; 15int r; 16int sum; 17int laz; 18 }tree[maxn< < 3]; 19 void init() 20 { 21memset(tree,0,sizeof(tree)); 22memset(e,0,sizeof(e)); 23memset(v,0,sizeof(v)); 24memset(u,0,sizeof(u)); 25memset(in,0,sizeof(in)); 26memset(vis,0,sizeof(vis)); 27memset(head,-1,sizeof(head)); 28cnt=0; 29 } 30 void dfs(int x) 31 { 32++num; 33v[x]=num; 34vis[x]=1; 35for(int i=head[x]; i!=-1; i=e[i].nex) 36{ 37int t=e[i].to; 38if(vis[t]==1) 39continue; 40dfs(t); 41} 42u[x]=num; 43 } 44 void add(int x,int y) 45 { 46e[cnt].to=y; 47e[cnt].nex=head[x]; 48head[x]=cnt++; 49 } 50 void pushdown(int cur) 51 { 52if(tree[cur].laz!=0) 53{ 54tree[cur< < 1].laz=tree[cur< < 1|1].laz=tree[cur].laz; 55tree[cur< < 1].sum=tree[cur< < 1|1].sum=tree[cur].laz; 56tree[cur].laz=0; 57} 58return; 59 } 60 61 void build(int l,int r,int cur) 62 { 63tree[cur].l=l; 64tree[cur].r=r; 65tree[cur].laz=0; 66tree[cur].sum=0; 67if(l==r) 68{ 69return; 70} 71int mid=(l+r)/2; 72build(l,mid,cur< < 1); 73build(mid+1,r,cur< < 1|1); 74 } 75 void update(int pl,int pr,int num,int cur) 76 { 77if(pl< =tree[cur].l& & tree[cur].r< =pr) 78{ 79tree[cur].laz=num; 80tree[cur].sum=num; 81return; 82} 83pushdown(cur); 84int mid=(tree[cur].l+tree[cur].r)/2; 85if(pl< =mid) 86update(pl,pr,num,cur< < 1); 87if(pr> =mid+1) 88update(pl,pr,num,cur< < 1|1); 89 } 90 int query(int pl,int pr,int cur)//一定要注意query中不能缺少pushdown 91 { 92if(pl< =tree[cur].l& & tree[cur].r< =pr) 93{ 94return tree[cur].sum; 95} 96//int ans=0; 97pushdown(cur); 98int mid=(tree[cur].l+tree[cur].r)/2; 99if(pl< =mid) 100return query(pl,pr,cur< < 1); 101if(pr> =mid+1) 102return query(pl,pr,cur< < 1|1); 103 } 104 int main() 105 { 106int T; 107int n,m; 108int a,b; 109cin> > T; 110int id=1; 111while(T--) 112{ 113num=0; 114init(); 115scanf("%d",& n); 116for(int i=1; i< =n-1; i++) 117{ 118scanf("%d%d",& a,& b); 119add(b,a); 120in[a]++; 121} 122for(int i=1; i< =n; i++) 123{ 124if(in[i]==0) 125{ 126dfs(i); 127break; 128} 129} 130char s[5]; 131build(1,n,1); printf("Case #%d: ",id++); 132scanf("%d",& m); 133while(m--) 134{ 135scanf("%s",s); 136if(s[0]==‘C‘) 137{ 138scanf("%d",& a); 139int ans=query(v[a],u[a],1); 140if(ans==0) 141printf("-1 "); 142else 143printf("%d ",ans); 144} 145if(s[0]==‘T‘) 146{ 147scanf("%d%d",& a,& b); 148update(v[a],u[a],b,1); 149} 150} 151} 152 }