HDU 3974 Assign the task (DFS序 + 线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3974

给你T组数据，n个节点，n-1对关系，右边的是左边的父节点，所有的值初始化为-1，然后给你q个操作：

有两种操作：

　　操作一：T X Y ，将以X为根的子树上的所有节点都变成Y。

　　操作二：C X，查询第X号点是多少？

没想到是线段树做，就算想到了也想不到用dfs序做...

例子中给你了这样的树：

3 5

4 1

DFS一遍转化成DFS序：2344113552

然后记录下每个数字最左边和最右边的位置，如：left[3] = 2, right[3] = 7。

因为是DFS序，所以他的子节点的范围一定包含在他的左右位置中。

所以就变成了很明显的线段树成段更新...

注意一点的是，查询是单点更新...

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int MAXN = 1e5 + 5;
  6 const int INF = 1e9 + 7;
  7 struct segtree {
  8     int l , r , val , lazy;
  9 }T[MAXN << 2];
 10 struct data {
 11     int next , to;
 12 }edge[MAXN];
 13 int head[MAXN] , cont , L[MAXN] , R[MAXN];
 14 //链式前向星
 15 inline void add(int u , int v) {
 16     edge[cont].to = v;
 17     edge[cont].next = head[u];
 18     head[u] = cont++;
 19 }
 20 //DFS序
 21 void dfs(int u) {
 22     L[u] = min(L[u] , ++cont);
 23     R[u] = max(R[u] , cont);
 24     for(int i = head[u] ; ~i ; i = edge[i].next) {
 25         int v = edge[i].to;
 26         dfs(v);
 27     }
 28     L[u] = min(L[u] , ++cont);
 29     R[u] = max(R[u] , cont);
 30 }
 31 
 32 void init(int p , int l , int r) {
 33     int mid = (l + r) >> 1;
 34     T[p].l = l , T[p].r = r , T[p].lazy = 0;
 35     if(l == r) {
 36         T[p].val = -1;
 37         return ;
 38     }
 39     init(p << 1 , l , mid);
 40     init((p << 1)|1 , mid + 1 , r);
 41 }
 42 
 43 void updata(int p , int l , int r , int val) {
 44     int mid = (T[p].l + T[p].r) >> 1;
 45     if(l == T[p].l && T[p].r == r) {
 46         T[p].val = val;
 47         T[p].lazy = val;
 48         return ;
 49     }
 50     if(T[p].lazy) {
 51         T[p << 1].val = T[(p << 1)|1].val = T[p << 1].lazy = T[(p << 1)|1].lazy = T[p].lazy;
 52         T[p].lazy = 0;
 53     }
 54     if(r <= mid) {
 55         updata(p << 1 , l , r , val);
 56     }
 57     else if(l > mid) {
 58         updata((p << 1)|1 , l , r , val);
 59     }
 60     else {
 61         updata(p << 1 , l , mid , val);
 62         updata((p << 1)|1 , mid + 1 , r , val);
 63     }
 64 }
 65 
 66 int query(int p , int index) {
 67     int mid = (T[p].l + T[p].r) >> 1;
 68     if(index == T[p].l && T[p].r == index) {
 69         return T[p].val;
 70     }
 71     if(T[p].lazy) {
 72         T[p << 1].val = T[(p << 1)|1].val = T[p << 1].lazy = T[(p << 1)|1].lazy = T[p].lazy;
 73         T[p].lazy = 0;
 74     }
 75     if(index <= mid) {
 76         return query(p << 1 , index);
 77     }
 78     else {
 79         return query((p << 1)|1 , index);
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int t , n , u , v , root , q;
 86     char str[5];
 87     scanf("%d" , &t);
 88     for(int ca = 1 ; ca <= t ; ca++) {
 89         scanf("%d" , &n);
 90         cont = 0 , root = (n + 1) * n / 2;
 91         for(int i = 1 ; i <= n ; i++) {
 92             R[i] = head[i] = -1;
 93             L[i] = INF;
 94         }
 95         for(int i = 1 ; i < n ; i++) {
 96             scanf("%d %d" , &u , &v);
 97             root -= u;
 98             add(v , u);
 99         }
100         cont = 0;
101         dfs(root);
102         init(1 , 1 , cont);
103         printf("Case #%d:
" , ca);
104         scanf("%d" , &q);
105         while(q--) {
106             scanf("%s" , str);
107             if(str[0] == 'T') {
108                 scanf("%d %d" , &u , &v);
109                 updata(1 , L[u] , R[u] , v);
110             }
111             else {
112                 scanf("%d" , &u);
113                 printf("%d
" , query(1 , L[u]));
114             }
115         }
116     }
117 }