给定一棵树，初始时树为空
操作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 ;
}