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就是有水的

 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
 #include <algorithm>
 #include <iostream>
 #include <queue>
 #include <stack>
 #include <vector>
 #include <map>
 #include <set>
 #include <string>
 #include <math.h>
 using namespace std;
 #pragma warning(disable:4996)
 #pragma comment(linker, "/STACK:1024000000,1024000000")
 typedef long long LL;
 const int INF = <<;
 /*
 我们对树进行dfs，求出dfs序列 in[]  和out[]   用线段树维护这个序列
 操作1就是将[in[b],out[b]]区间内的点都变为1 ，  如果区间内存在0，那么要将b的父结点更新为0，因为虽然更新了[in[b],out[b]]，但是祖先不会变
 操作2就是将点in[b]置为0
 操作3就是看区间[in[b],out[b]]  所以不仅可以将树进行树链剖分，然后用线段树维护
 还可以用线段树维护树的dfs序列
 */
 const int N =  + ;
 int in[N], out[N], num, fa[N];
 int tree[N * ], laze[N * ];
 vector<int> g[N];
 void dfs(int u)
 {
     in[u] = ++num;
     for (int i = ; i < g[u].size(); ++i)
     {
         int v = g[u][i];
         if (v != fa[u])
         {
             fa[v] = u;
             dfs(v);
         }
     }
     out[u] = num;
 }
 void pushDown(int rt)
 {
     if (laze[rt]==)
     {
         tree[rt << ] = tree[rt <<  | ] = laze[rt << ] = laze[rt <<  | ] = ;
         laze[rt] = ;
     }
 }
 void pushUp(int rt)
 {
     if (tree[rt << ] ==  || tree[rt <<  | ] == )
         tree[rt] = ;
     else
         tree[rt] = ;
 }
 bool flag = false;
 void update(int l, int r, int rt, int L, int R, int val)
 {
     pushDown(rt);
     if (L<=l && R>=r)
     {
         if (tree[rt] == )
             flag = true;
         tree[rt] = val;
         laze[rt] = val;
         return;
     }
     int mid = (l + r) >> ;
     if (L <= mid)
         update(l, mid, rt << , L, R, val);
     if (R > mid)
         update(mid + , r, rt <<  | , L, R, val);
     pushUp(rt);
 } void query(int l, int r, int rt, int L, int R)
 {
     pushDown(rt);
     if (L<=l && R>=r)
     {
         //区间内有一个是0，那么所访问的点（根）就是0
         if (tree[rt] == )
             flag = false;
         return;
     }
     int mid = (l + r) >> ;
     if (L <= mid)
         query(l, mid, rt << , L, R);
     if (R > mid)
         query(mid + , r, rt <<  | , L, R);
     pushUp(rt);
 }
 int main()
 {
     //freopen("d:/in.txt", "r", stdin);
     int n, q, a, b,x, y;
     scanf("%d", &n);
     for (int i = ; i < n; ++i)
     {
         scanf("%d%d", &a, &b);
         g[a].push_back(b);
         g[b].push_back(a);
     }
     fa[] = ;
     dfs();
     scanf("%d", &q);
     while (q--)
     {
         scanf("%d%d", &a, &b);
         if (a == )
         {
             flag = false;
             //将区间内的点都置为1
             update(,  n, , in[b], out[b],);
             //如果区间内存在0的点，那么fa[b]肯定为空，
             if (flag&&fa[b]!=)
             {
                 update(,  n, , in[fa[b]],in[fa[b]],);
             }
         }
         else if (a == )
         {
             update(,  n, , in[b],in[b],);
         }
         else
         {
             flag = true;
             query(,n, , in[b], out[b]);
             if (flag)
                 printf("1\n");
             else
                 printf("0\n");
         }
     }
     return ;
 }