Assign the task HDU

有一家公司有N个员工(从1到N)，公司里每个员工都有一个直接的老板(除了整个公司的领导)。如果你是某人的直接老板，那个人就是你的下属，他的所有下属也都是你的下属。如果你是没有人的老板，那么你就没有下属，没有直接老板的员工就是整个公司的领导，也就是说N个员工构成了一棵树。公司通常把一些任务分配给一些员工来完成，当一项任务分配给某个人时，他/她会把它分配给他/她的所有下属，换句话说，这个人和他/她的所有下属在同一时间接受了一项任务。此外，每当员工收到一个任务，他/她将停止当前任务(如果他/她有)，并开始新的任务。在公司将某些任务分配给某个员工后，编写一个程序来帮助找出某个员工当前的任务。

Input第一行包含单个正整数T(T<=10)，表示测试用例的数量。对于每个测试用例：第一行包含一个整数N(N≤50，000)，它是雇员的数目。下面的N-1行分别包含两个整数u和v，这意味着雇员v是雇员u的直接老板(1<=u，v<=N)。下一行包含一个整数M(M≤50，000)。下面的M行分别包含一条消息，“Cx”表示对员工x的当前任务的查询，“Tx y”表示公司将任务y分配给员工x。(1<=x<=N，0<=y<=10^9)Output对于每个测试用例，在第一行打印测试用例编号(以1开头)，然后为每个查询输出相应的答案。Sample Input

Sample Output

Case #1:
-1 
1 
2

分析：用dfs遍历多叉树，按遍历顺序给每个人编号并保存子树的区间，然后直接套线段树的模板，进行区间的更新（子树的区间是连续的）；

代码：

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 const int maxn = 5 * 1e4 + 10;
  4 struct bo
  5 {
  6     int l, r;
  7     int task;
  8 }t[maxn << 2];
  9 
 10 int n;
 11 int clockk;
 12 bool vis[maxn];
 13 vector<int> bos[maxn];
 14 int l[maxn], r[maxn];
 15 
 16 void pushdown(int tar)
 17 {
 18     if (t[tar].task != -1)
 19     {
 20         t[tar << 1].task = t[tar << 1 | 1].task = t[tar].task;
 21         t[tar].task = -1;
 22     }
 23 }
 24 
 25 void build(int l, int r, int tar)
 26 {
 27     t[tar].l = l, t[tar].r = r, t[tar].task = -1;
 28     if (l == r) return;
 29     int mid = (l + r) >> 1;
 30     build(l, mid, tar << 1);
 31     build(mid + 1, r, tar << 1 | 1);
 32 }
 33 void dfs(int x)
 34 {
 35     l[x] = ++clockk;
 36     for (int i = 0; i < bos[x].size(); i++)
 37         dfs(bos[x][i]);
 38     r[x] = clockk;
 39 }
 40 
 41 void update(int l, int r, int work, int tar)
 42 {
 43     if (t[tar].l == l && t[tar].r == r)
 44     {
 45         t[tar].task = work;
 46         return;
 47     }
 48     pushdown(tar);
 49     int mid = (t[tar].l + t[tar].r) >> 1;
 50     if (r <= mid) update(l, r, work, tar << 1);
 51     else if (l > mid) update(l, r, work, tar << 1 | 1);
 52     else update(l, mid, work, tar << 1), update(mid + 1, r, work, tar << 1 | 1);
 53 }
 54 
 55 int query(int x, int tar)
 56 {
 57     if (t[tar].l == t[tar].r) return t[tar].task;
 58     pushdown(tar);
 59     int mid = (t[tar].l + t[tar].r) >> 1;
 60     if (x <= mid) return query(x, tar << 1);
 61     else return query(x, tar << 1 | 1);
 62 }
 63 
 64 int main()
 65 {
 66     int T; cin >> T;
 67     int boss, emp;
 68     char ope[3];
 69     int cases = 0;
 70 
 71     while (T--)
 72     {
 73         cin >> n;
 74         clockk = 0;
 75         memset(vis, 0, sizeof(vis));
 76         for (int i = 1; i <= n; i++)
 77             bos[i].clear();
 78         build(1, n, 1);
 79         for (int i = 1; i < n; i++)
 80         {
 81             scanf("%d%d", &emp, &boss);
 82             vis[emp] = true;
 83             bos[boss].push_back(emp);
 84         }
 85         for (int i = 1; i <= n; i++)
 86             if (!vis[i])
 87                 dfs(i);
 88         int m, x, y;
 89 
 90         cin >> m;
 91         printf("Case #%d:
", ++cases);
 92         while (m--)
 93         {
 94             cin >> ope;
 95             if (ope[0] == 'C')
 96             {
 97                 scanf("%d", &x);
 98                 cout << query(l[x], 1) << endl;
 99             }
100             else
101             {
102                 scanf("%d%d", &x, &y);
103                 update(l[x], r[x], y, 1);
104             }
105         }
106     }
107 }