题目描述

Deni 是一家公司的老板，公司共有 N 名员工，编号为 1..N。

公司的管理结构是严格层级化的：除 1 号员工外，每个员工都恰好有一个直接上级。因此整家公司构成一棵以 1 为根的有根树。

对于某个员工 x：

• x 自己称为 x 的 0 级下属；
• x 的直接下级称为 1 级下属；
• 这些人的直接下级称为 2 级下属；
• 依此类推。

现在公司里有一条突发新闻，开始时只有部分员工知道。

Deni 会进行多次操作。每次她选择一个员工 x 和一个整数 k，然后把新闻告诉 x 的所有 0,1,2,...,k 级下属。我们把这些人统称为 x 的 k-下属。

Deni 想维护一个系统，支持以下两类操作：

1. 1 x k：把新闻告诉 x 的所有 k-下属；
2. 2 x k：询问在 x 的所有 k-下属中，目前有多少人已经知道这条新闻。

请你处理所有询问。

输入格式

第一行一个整数 N，表示员工数量。

接下来 N-1 行，每行两个整数 x, y，表示员工 y 是员工 x 的直接下属。

接下来一行包含 N 个整数 b_1, b_2, ..., b_N：

• b_i = 1 表示员工 i 初始时已经知道新闻；
• b_i = 0 表示员工 i 初始时不知道新闻。

接下来一行一个整数 Q，表示操作数。

接下来 Q 行，每行描述一个操作，格式如题目描述所示。

输出格式

对于每个类型为 2 的询问，按输入顺序各输出一行，表示答案。

样例 #1

输入 #1

10
1 2
1 3
3 4
3 5
3 6
4 7
4 8
8 9
8 10
0 1 0 1 0 1 0 1 0 1
9
2 1 1
2 4 4
2 3 0
1 1 2
2 3 4
1 4 1
2 1 1
2 4 4
2 3 2

输出 #1

1
3
0
6
3
4
6

样例解释

初始时知道新闻的员工为 2,4,6,8,10。

例如第一次询问 2 4 4 中，员工 4 的 4-下属为 4,7,8,9,10，其中 4,8,10 已知新闻，因此答案为 3。

在操作 1 4 1 后，员工 4 的 1-下属为 4,7,8，其中只有 7 会新获得新闻。

数据范围

• 2 <= N <= 2 * 10^5
• 1 <= Q <= 2 * 10^5
• 0 <= k <= N

子任务

只有通过某个子任务中的所有测试点，才能获得该子任务的全部分数。