# Hdu3974 assign the task segment tree DFS order

The theme is ：
Disorderly numbered as 1-n The staff of our company arrange the superior and subordinate ,
Operation 1 ： Give an employee a task C, Then the employee and his subordinate tasks are replaced by tasks C
Operation two ： Ask an employee , Back to his mission

Explanation :
Give an employee a task , Then his group will change , Think of the interval modification of the line segment tree , But this is for one person , It's not an interval operation , If you can put the “ Point ” The operation becomes “ Interval ” The operation responsibility problem is transformed into interval modification and single point query , Here dfs The order maps the points of the original state to a line

dfs order ：
Find a spot without a father
Find out his l and r, Add one every time you enter , Return without
No      1 2 3 4 5
Left end point 4 1 3 5 2
Right endpoint 4 5 5 5 2
namely 2 He went to the left at No 1, Right end to 5

Single point query ：
Inquire about x, It can be understood as a query l[x] or r[x]（ Subordinates are in line with their own work ）
Interval modification ：
For example, the picture above changes 2 That is to change 1,5

```  1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+90;
4 const int inf=1e9+90;
5 #define eps 1e-10
6 #define forn(i,n) for(int i=0;i<n;i++)
7 #define form(i,n) for(int i=1;i<=n;i++)
8 typedef long long ll ;
9 typedef unsigned long long ull ;
10 #define ls l,mid,p<<1
11 #define rs mid+1,r,p<<1|1
12 int a[N];
13 int n,m,root,rt;
14 int to[N],ver[N],h[N],tot;
15 char c[2];
16 void add(int x,int y){
17     to[++tot]=h[x];
18     ver[tot]=y;
19     h[x]=tot;
20 }
21 struct Node{
22     int l,r;
23     ll sum;
24 }t[N<<2];
25 int ml[N],mr[N];
26 void dfs(int x){
27     // When I came in +1,
28     ml[x]=++rt;
29     for(int i=h[x];~i;i=to[i]){
30         dfs(ver[i]);
31     }
32     mr[x]=rt;// You don't need to go back +1
33 }
34 void pd(int p){
35     if(t[p].sum!=-1){
36         t[p<<1].sum=t[p<<1|1].sum=t[p].sum;
37         t[p].sum=-1;
38     }
39 }
40 void build(int l,int r,int p){
41     if(l==r){
42         t[p].l=t[p].r=l;
43         t[p].sum=-1;
44         return;
45     }
46     t[p]={l,r,-1};
47     int mid=l+r>>1;
48     build(l,mid,p<<1);
49     build(mid+1,r,p<<1|1);
50 }
51 void modify(int l,int r,int c,int p){
52     if(l<=t[p].l&&t[p].r<=r){
53         t[p].sum=c;
54         return;
55     }
56     pd(p);
57     int mid=t[p].l+t[p].r>>1;
58     if(l<=mid)modify(l,r,c,p<<1);
59     if(r>mid)modify(l,r,c,p<<1|1);
60 }
61 int query(int x,int p){
62     if(t[p].l==t[p].r)return t[p].sum;
63     pd(p);
64     int mid=t[p].l+t[p].r>>1;
65     int ans=-1;
66     if(x<=mid)ans=query(x,p<<1);
67     else ans=query(x,p<<1|1);
68     return ans;
69 }
70 int main(){
71 //    freopen("in.txt","r",stdin);
72 //    freopen("out.txt","w",stdout);
73     int T,x,y;
74     cin>>T;
75     form(k,T){
76         printf("Case #%d:\n",k);
77         scanf("%d",&n);
78         memset(a,0,sizeof(a));
79         memset(h,-1,sizeof(h));
80         tot=0,rt=0;
81         forn(i,n-1) {
82             scanf("%d%d", &x, &y);
84             a[x] = 1;
85         }
86         form(i,n){
87             if(!a[i]){
88                 root=i;
89                 break;
90             }
91         }
92         scanf("%d",&m);
93         dfs(root);
94         build(1,n,1);
95         forn(i,m){
96             scanf("%s",c);
97             if(c[0]=='C'){
98                 scanf("%d",&x);
99                 printf("%d\n",query(ml[x],1));
100             }else{
101                 scanf("%d%d",&x,&y);
102                 modify(ml[x],mr[x],y,1);
103             }
104         }
105     }
106 }```