CF343D.Water Tree

Mad scientist Mike has constructed a rooted tree, which consists of n vertices. Each vertex is a reservoir which can be either empty or filled with water.

The vertices of the tree are numbered from 1 to n with the root at vertex 1. For each vertex, the reservoirs of its children are located below the reservoir of this vertex, and the vertex is connected with each of the children by a pipe through which water can flow downwards.

Mike wants to do the following operations with the tree:

1. Fill vertex v with water. Then v and all its children are filled with water.
2. Empty vertex v. Then v and all its ancestors are emptied.
3. Determine whether vertex v is filled with water at the moment.

Initially all vertices of the tree are empty.

Mike has already compiled a full list of operations that he wants to perform in order. Before experimenting with the tree Mike decided to run the list through a simulation. Help Mike determine what results will he get after performing all the operations.

疯狂科学家迈克构建了一棵有根树，该树包含 $n$ 个顶点。每个顶点是一个蓄水池，可以处于空或注满水两种状态。

树的顶点编号为 $1$ 到 $n$，其中顶点 $1$ 为树根。对于任意顶点，其子节点所对应的蓄水池均位于该顶点蓄水池的下方，并且该顶点通过管道与每个子节点相连，水可沿管道向下流动。

迈克希望对这棵树执行以下操作：

1. 向顶点 $v$ 注水。此后，$v$ 及其所有后代顶点均被注满水。
2. 清空顶点 $v$。此后，$v$ 及其所有祖先顶点均被清空。
3. 查询当前顶点 $v$ 是否处于注满水的状态。

初始时，树中所有顶点均为空。

迈克已预先整理出一份他打算按顺序执行的操作列表。在实际对树进行实验之前，迈克决定先对该操作列表进行一次模拟。请帮助迈克确定：在执行完全部操作后，每次查询操作将得到怎样的结果。

The first line of the input contains an integer n (1 ≤ n ≤ 500000) — the number of vertices in the tree. Each of the following n - 1 lines contains two space-separated numbers a__i, b__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i) — the edges of the tree.

The next line contains a number q (1 ≤ q ≤ 500000) — the number of operations to perform. Each of the following q lines contains two space-separated numbers c__i (1 ≤ c__i ≤ 3), v__i (1 ≤ v__i ≤ n), where c__i is the operation type (according to the numbering given in the statement), and v__i is the vertex on which the operation is performed.

It is guaranteed that the given graph is a tree.

输入的第一行包含一个整数 $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$ 表示执行操作的顶点。

保证给定的图是一棵树。

For each type 3 operation print 1 on a separate line if the vertex is full, and 0 if the vertex is empty. Print the answers to queries in the order in which the queries are given in the input.

对于每个类型 3 的操作，如果该顶点已满，则在单独一行输出 1；如果该顶点为空，则输出 0。请按照输入中查询给出的顺序输出查询的答案。