Codeforces Round #200 (Div. 1)D. Water Tree

题意： 

对一棵树有三种操作：

1. 将以x为根的子树全部置1
2. 将x置0，并将其祖先结点都置0
3. 查询以x为根的子树上是不是所有结点都为1

思路：

1. 首先得到树的dfs序，对dfs序建线段树
2. 置0操作：将以x为根的这个子树对应的的所有线段树区间都置0。单点更新：将in[x]叶子结点置0，那么pushup上去，所有的祖先结点都是0
3. 查询操作：判断以x为根的子树上所有结点是不是有0，有0，那它肯定是0. 区间更新[ in[x], out[x] ]
4. 置1操作：判断以x为根的子树是不是为0，如果为0，那它的父亲结点一定是0，更新它的父亲结点in[ Fa[x] ]为0。然后置1[ in[x], out[x] ]

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define lowbit(x) x & (-x)#define MID (l + r ) >> 1
#define lsn rt << 1
#define rsn rt << 1 | 1
#define Lson lsn, l, mid
#define Rson rsn, mid + 1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define eps  1e-6using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxN = 5e5 + 5;
inline int read()
{int x = 0, f = 1; char c = getchar();while(c < '0' || c > '9') { if(c == '-') f = -f; c = getchar(); }while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }return x * f;
}
int n;
struct EDGE{int adj, to;EDGE(int a = -1, int b = 0): adj(a), to(b) {}
}edge[maxN << 1];
int head[maxN], cnt;
void init()
{memset(head, -1, sizeof(head));cnt = 0;
}
void add_edge(int u, int v)
{edge[cnt] = EDGE(head[u], v);head[u] = cnt ++;
}
int F[maxN];
int in[maxN], out[maxN], time;
void dfs(int x, int fa)
{in[x] = ++ time;F[x] = fa;for(int i = head[x]; ~i; i = edge[i].adj){if(edge[i].to == fa)continue;dfs(edge[i].to, x);}out[x] = time;
}
int tree[maxN << 2];
void pushup(int rt) { tree[rt] = tree[lsn] & tree[rsn]; }
void build_tree(int rt, int l, int r)
{tree[rt] = 0;if(l == r) return ;int mid = MID;build_tree(Lson);build_tree(Rson);
}
//只有当父亲结点有水时才需要往下推，否则不需要
void pushdown(int rt)
{if(tree[rt])tree[lsn] = tree[rsn] = tree[rt];
}
//更新时，如果是灌满水，用到子孙结点，就直接下推即可，tree[rt]可充当标记数组
//如果是清空，那么就将叶子结点更新为0，那么再pushup上去，它的祖先结点就都是0
void update(int rt, int l, int r, int ql, int qr, int val)
{if(ql <= l && qr >= r){tree[rt] = val;return;}pushdown(rt);int mid = MID;if(ql <= mid) update(QL, val);if(qr > mid) update(QR, val);pushup(rt);
}
//查询时，只要子树中有一个子孙是0，那它就是0
int query(int rt, int l, int r, int ql, int qr)
{if(ql <= l && qr >= r) return tree[rt];pushdown(rt);int mid = MID;int res = 1;if(ql <= mid) res = res & query(QL);if(qr > mid) res = res & query(QR);return res;
}
int main()
{init();n = read();for(int i = 0; i < n - 1; i ++ ){int u, v; u = read(); v = read();add_edge(u, v); add_edge(v, u);}dfs(1, 0);int q; q = read();while(q -- ){int op, x; op = read(); x = read();if(op == 1)//填满//它和它的子孙都是1{//需要查询这个子树本身是不是0，如果是0，那么更新它的父亲是0if(x > 1 && query(1, 1, n, in[x], out[x]) == 0)update(1, 1, n, in[F[x]], in[F[x]], 0);update(1, 1, n, in[x], out[x], 1);}else if(op == 2)//清空//它和它的祖先都是0{update(1, 1, n, in[x], in[x], 0);}else//查询{printf("%d\n", query(1, 1, n, in[x], out[x]));}}return 0;
}