CodeForces 343D 线段树维护dfs序

给定一棵树，初始时树为空

操作1，往某个结点注水，那么该结点的子树都注满了水

操作2，将某个结点的水放空，那么该结点的父亲的水也就放空了

操作3，询问某个点是否有水

我们将树进行dfs，生成in[u]，访问结点u的时间戳，out[u]，离开结点u的时间戳

每个结点的in值对应在线段树中的区间的一点

那么对于操作1，只要将区间[in[u],out[u]] 的值都改为1, 但是如果区间[in[u],out[u]] 原先存在为0的点，那么父区间肯定是空的，这个操作不能

改变父区间的状态，所以需要将in[fa[u]]置为0,

对于操作2，只要将in[u] 置为0就行了

对于操作3，只要区间[in[u],out[u]]内不存在为0的点，那么点u就是有水的

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <stdlib.h>
  4 #include <algorithm>
  5 #include <iostream>
  6 #include <queue>
  7 #include <stack>
  8 #include <vector>
  9 #include <map>
 10 #include <set>
 11 #include <string>
 12 #include <math.h>
 13 using namespace std;
 14 #pragma warning(disable:4996)
 15 #pragma comment(linker, "/STACK:1024000000,1024000000")
 16 typedef long long LL;                   
 17 const int INF = 1<<30;
 18 /*
 19 我们对树进行dfs，求出dfs序列 in[]  和out[]   用线段树维护这个序列
 20 操作1就是将[in[b],out[b]]区间内的点都变为1 ，  如果区间内存在0，那么要将b的父结点更新为0，因为虽然更新了[in[b],out[b]]，但是祖先不会变
 21 操作2就是将点in[b]置为0
 22 操作3就是看区间[in[b],out[b]] 
 23 
 24 
 25 所以不仅可以将树进行树链剖分，然后用线段树维护
 26 还可以用线段树维护树的dfs序列
 27 */
 28 const int N = 500000 + 10;
 29 int in[N], out[N], num, fa[N];
 30 int tree[N * 8], laze[N * 8];
 31 vector<int> g[N];
 32 void dfs(int u)
 33 {
 34     in[u] = ++num;
 35     for (int i = 0; i < g[u].size(); ++i)
 36     {
 37         int v = g[u][i];
 38         if (v != fa[u])
 39         {
 40             fa[v] = u;
 41             dfs(v);
 42         }
 43     }
 44     out[u] = num;
 45 }
 46 void pushDown(int rt)
 47 {
 48     if (laze[rt]==1)
 49     {
 50         tree[rt << 1] = tree[rt << 1 | 1] = laze[rt << 1] = laze[rt << 1 | 1] = 1;
 51         laze[rt] = 0;
 52     }
 53 }
 54 void pushUp(int rt)
 55 {
 56     if (tree[rt << 1] == 0 || tree[rt << 1 | 1] == 0)
 57         tree[rt] = 0;
 58     else
 59         tree[rt] = 1;
 60 }
 61 bool flag = false;
 62 void update(int l, int r, int rt, int L, int R, int val)
 63 {
 64     pushDown(rt);
 65     if (L<=l && R>=r)
 66     {
 67         if (tree[rt] == 0)
 68             flag = true;
 69         tree[rt] = val;
 70         laze[rt] = val;
 71         return;
 72     }
 73     int mid = (l + r) >> 1;
 74     if (L <= mid)
 75         update(l, mid, rt << 1, L, R, val);
 76     if (R > mid)
 77         update(mid + 1, r, rt << 1 | 1, L, R, val);
 78     pushUp(rt);
 79 }
 80 
 81 void query(int l, int r, int rt, int L, int R)
 82 {
 83     pushDown(rt);
 84     if (L<=l && R>=r)
 85     {
 86         //区间内有一个是0，那么所访问的点（根）就是0
 87         if (tree[rt] == 0)
 88             flag = false;
 89         return;
 90     }
 91     int mid = (l + r) >> 1;
 92     if (L <= mid)
 93         query(l, mid, rt << 1, L, R);
 94     if (R > mid)
 95         query(mid + 1, r, rt << 1 | 1, L, R);
 96     pushUp(rt);
 97 }
 98 int main()
 99 {
100     //freopen("d:/in.txt", "r", stdin);
101     int n, q, a, b,x, y;
102     scanf("%d", &n);
103     for (int i = 1; i < n; ++i)
104     {
105         scanf("%d%d", &a, &b);
106         g[a].push_back(b);
107         g[b].push_back(a);
108     }
109     fa[1] = 0;
110     dfs(1);
111     scanf("%d", &q);
112     while (q--)
113     {
114         scanf("%d%d", &a, &b);
115         if (a == 1)
116         {
117             flag = false;
118             //将区间内的点都置为1
119             update(1,  n, 1, in[b], out[b],1);
120             //如果区间内存在0的点，那么fa[b]肯定为空，
121             if (flag&&fa[b]!=0)
122             {
123                 update(1,  n, 1, in[fa[b]],in[fa[b]],0);
124             }
125         }
126         else if (a == 2)
127         {
128             update(1,  n, 1, in[b],in[b],0);
129         }
130         else
131         {
132             flag = true;
133             query(1,n, 1, in[b], out[b]);
134             if (flag)
135                 printf("1
");
136             else
137                 printf("0
");
138         }
139     }
140     return 0;
141 }