通过dfs序建立线段树

// 题意机器翻译: 有一家公司有N名员工（从1到N），公司中的每个员工都有直属上司（整个公司的负责人除外）。如果您是某人的直属上司，那么该人就是您的下属，他所有的下属也是你的下属如果您没有老板，那么您就没有下属，没有直接上司的员工就是整个公司的领导者。因此，这意味着N名员工组成了一棵树。
公司通常将一些任务分配给某些员工以完成任务。当任务分配给某人时，他/她会将其分配给他/她的所有下属。换句话说，此人及其所有下属在任务中都收到了任务。同时。此外，员工收到任务后，将停止当前任务（如果有）并开始新任务。
在公司将某些任务分配给某位员工之后，编写一个有助于确定某位员工当前任务的程序。

// 第一行包含一个正整数T（T <= 10），表示测试用例的数量。
对于每个测试用例：
第一行包含一个整数N（N≤50,000），它是员工人数。
接下来的N-1行每行包含两个整数u和v，这表示雇员v是雇员u（1 <= u，v <= N）的直接老板。
下一行包含一个整数M（M≤50,000）。
接下来的M行每行包含一条消息“ C x”，这意味着查询雇员x的当前任务，“ T x y”，这意味着公司将任务y分配给了雇员x。（1 <= x <= N，0 <= y <= 10 ^ 9）

 1 #include<cstdio>
 2 #include<vector>
 3 #define L k<<1
 4 #define R k<<1|1
 5 #define mid (tree[k].l+tree[k].r)>>1
 6 using namespace std;
 7 
 8 const int MAXN = 50000+5;
 9 
10 struct segmemt {
11     int l, r, w;// w表示当前任务(起始为-1)
12     int f;
13 } tree[4*MAXN+1];
14 
15 vector<int> G[MAXN];
16 int out[MAXN];
17 int num;// dfs序的时间戳
18 int s[MAXN], e[MAXN];// 点x在线段树区间的两端点标号。s[x]~~e[x]内的值都是他的下属
19 
20 inline void dfs(int x) {
21     s[x] = ++num;
22     int sz = G[x].size();
23     for(int i = 0; i != sz; ++i) dfs(G[x][i]);
24     e[x] = ++num;
25 }
26 
27 inline void build(int k, int l, int r) {
28     tree[k].l = l, tree[k].r = r;
29     tree[k].w = -1;
30     tree[k].f = 0;
31     if(l == r) return ;
32     int m = (l + r) >> 1;
33     build(L, l, m);
34     build(R, m+1, r);
35 }
36 
37 inline void down(int k) {
38     tree[L].w = tree[R].w = tree[k].w;
39     tree[L].f = tree[R].f = 1;
40     tree[k].f = 0;
41 }
42 
43 inline void change_interval(int k, int x, int y, int v) {
44     if(tree[k].l >= x && tree[k].r <= y) {
45         tree[k].w = v; tree[k].f = 1;
46         return;
47     }
48     if(tree[k].f) down(k);
49     int m = mid;
50     if(x <= m) change_interval(L, x, y, v);
51     if(y > m) change_interval(R, x, y, v);
52 }
53 
54 inline int query_point(int k, int x) {
55     if(tree[k].l == tree[k].r) return tree[k].w;
56     if(tree[k].f) down(k);
57     int m = mid;
58     if(x <= m) return query_point(L, x);
59     else return query_point(R, x);
60 }
61 
62 int main() {
63     int T, cnt = 1;
64     scanf("%d", &T);
65     int n, m;
66     int x, y;
67     char com[10];
68     while(T--) {
69         scanf("%d", &n);
70         for(int i = 1; i <= n; ++i) out[i] = 0, G[i].clear();
71         for(int i = 0; i != n-1; ++i) {
72             scanf("%d%d", &x, &y);
73             out[x] = 1;
74             G[y].push_back(x);
75         }
76         num = 0;
77         for(int i = 1; i <= n; ++i) {
78             if(!out[i]) { dfs(i); break; }
79         }
80         build(1, 1, num);
81         scanf("%d", &m);
82         printf("Case #%d:
", cnt++);
83         for(int i = 0; i != m; ++i) {
84             scanf("%s", com);
85             if(com[0] == 'T') {
86                 scanf("%d%d", &x, &y);
87                 change_interval(1, s[x], e[x], y);
88             }
89             else scanf("%d", &x), printf("%d
", query_point(1, s[x]));
90         }
91     }
92     return 0;
93 }