CF343D Water Tree

疯狂科学家 Mike 构造了一棵有根树，这棵树包含 $n$ 个顶点。每个顶点都是一个水库，可以为空或充满水。 树的顶点从 $1$ 到 $n$ 编号，根节点为 $1$ 号顶点。对于任意顶点，其所有子节点的水库都在该顶点的水库下方，每个顶点通过一根管道与每个子节点相连，水可以沿管道向下流动。 Mike 想要对这棵树进行以下操作： 1. 给顶点 $v$ 注水。那么 $v$ 及其所有子树中的顶点都会被注满水。 2. 清空顶点 $v$。那么 $v$ 及其所有祖先节点都会被清空。 3. 判断当前顶点 $v$ 是否充满水。 初始时所有顶点均为空。Mike 已经预先编写好了一系列操作顺序。在进行真正的实验前，他想先通过模拟来计算所有操作的结果。请帮助 Mike 模拟这些操作，并输出每次判断的结果。

第一行包含一个整数 $n$（$1 \leq n \leq 500000$），表示树的顶点数量。接下来的 $n-1$ 行每行包含两个用空格分隔的整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$），表示树上的一条无向边。 接下来一行包含一个整数 $q$（$1 \leq q \leq 500000$），表示操作的数量。接下来的 $q$ 行每行包含两个用空格分隔的整数 $c_i$（$1 \leq c_i \leq 3$）、$v_i$（$1 \leq v_i \leq n$），其中 $c_i$ 表示操作类型（与题目描述中的序号一致），$v_i$ 表示操作作用的顶点编号。 保证给定的图是一棵树。

对于每个类型为 3 的操作，若顶点当前为充满水，输出 $1$；否则输出 $0$。答案与查询输入顺序一致，每行输出一个结果。

由 ChatGPT 5 翻译