题意

在你面前有n个蓄水池，他们组成了树形结构（由n-1条边连接）。蓄水池节点编号从1开始到n。对每个蓄水池节点来说，他的儿子蓄水池节点都摆放在他的下面，并且和它用水管相连，根据重力，水会向下流动。现在我们要在蓄水池上做一些操作：
1. 把节点v填满水。然后v的所有儿子节点水也会被填满
2. 清空节点v的水。然后v所有的父亲节点水都会被清空
3. 询问每个蓄水池节点是否有水。
初始状态时候，每个节点都是空的。
现在我们会依次进行一系列操作，我们想提前知道每次操作后的结果，你能帮忙解决吗？

输入描述

第一行包含一个正整数n(1<=n<=1000)，表示蓄水池节点的数量。

后面n-1行，每行有两个数字a[i], b[i]。（1<=a[i], b[i]<= n, a[i]!=b[i])表示蓄水池的连接关系。

接下来的一行包含一个整数q(1<=q<=1000)，表示我们要进行的操作的数量。

最后的q行中，每行包含两个数字c[i] (1<=c[i]<=3)和v[i](1<=v[i]<=n)。
其中c[i]表示操作类型(1,2或者3)。v[i]表示操作对应的蓄水池节点。

输入数据保证合理，是一个连通的树。

输出描述

对于每个操作3（c[i] == 3)，输出一个数字1或者0。1表示v[i]蓄水池节点有水，0表示没水。

示例

输入

5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5

输出

0
0
0
1
0
1
0
1

dfs 与 懒标记

查找或者抽水的时候才更新

C++代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 1010;

int h[N], ne[N], e[N], w[N], idx;
int n, m;
bool st[N];
int found;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void update(int node, int son, int fa, bool state)
{
    bool oldstate = st[son];
    if(son == node){
        st[son] &= state;
        found = true;
    }

    for(int i = h[son]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j != fa){
            st[j] |= oldstate; // 子节点会被懒标记更新
            if(!found) update(node, j, son, state);
            st[son] &= st[j]; // 这里主要是根据后面的情况更新当前节点的状态
                              // state == false 会导致, 回溯时父节点状态改变为 false
                              // state == true 时不会改变, 相当于只是更新子节点状态
                              // 这也是为什么, 子节点更新用|, 而父节点更新用&
        }
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    while(-- n)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    cin >> m;
    while(m --)
    {
        int opt, node;
        cin >> opt >> node;
        if(1 == opt) st[node] = true;
        else if(2 == opt) {
            found = false;
            update(node, 1, -1, false);
        }
        else if(3 == opt){
            found = false;
            update(node, 1, -1, true);
            st[node] == true ? puts("1") : puts("0");
        }
    }

    return 0;
}