← 返回题目列表

Codeforces · 343/D

D. 水树

中文机器翻译题面 查看原题

疯狂科学家迈克构建了一棵有根树,由 n 个顶点组成。每个顶点都是一个水库,可以是空的,也可以是装满水的。

树的顶点从1到n编号,根在顶点1。对于每个顶点,其子节点的水库位于该顶点的水库下方,并且该顶点通过水可以向下流动的管道与每个子节点连接。

Mike 希望对树执行以下操作:

1. 用水填充顶点 v。然后 v 和它的所有子元素都充满了水。
2. 清空顶点 v。然后清空 v 及其所有祖先。
3、判断顶点v此时是否充满了水。

Mike 已经编制了他想要按顺序执行的操作的完整列表。在对树进行实验之前,迈克决定通过模拟运行该列表。帮助迈克确定执行所有操作后他会得到什么结果。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 500000) — 树中的顶点数。以下 n - 1 行中的每一行都包含两个以空格分隔的数字 ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — 树的边。

下一行包含数字 q (1 ≤ q ≤ 500000) — 要执行的操作数。以下 q 行中的每一行包含两个以空格分隔的数字 ci (1 ≤ ci ≤ 3)、vi (1 ≤ vi ≤ n),其中 ci 是操作类型(根据语句中给出的编号),vi 是执行操作的顶点。

保证给定的图是一棵树。

输出

对于每个类型 3 操作,如果顶点已满,则在单独的行上打印 1;如果顶点为空,则在单独的行上打印 0。按照输入中给出查询的顺序打印查询的答案。

示例

输入 #1

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

输出 #1

0
0
0
1
0
1
0
1