配点 : 500 点
問題文
N 由顶点组成的有根树 有 T 并且顶点是 它的编号为 1 到 N 。开始就是顶部 1 是根。
另外,N-1 在书的侧面中,i 第一条边是顶点 a_i 和顶点 表示 b_i 是平局。
各頂点 v 都是整数数组 我有 A_v 。最初一切都是空的。
这棵有根的树 执行 T 于 Q 查询操作。查询操作是 3 有不同的类型,如下所示。
1 v x k― 頂点 v 的子树中包含的任意顶点(vertex) v ) 对于 u , A_u 有一个值 添加 x 被 k 。2 v y z― 頂点 v 数组 A_v 中包含的元素中, 满足val xor y \leq z 的值 查找 val 的编号。在这里, 指s xor t 为 s 和 t 的按位异或。3 v- 根到顶点 更改为 v 。
您必须编写一个程序来按顺序处理此类查询。
制約
- 所有输入均为整数。
- 1 \leq N \leq 1.4 \times 10^5
- 1 \leq Q \leq 1.4 \times 10^5
- 1 \leq a_i, b_i \leq N (1 \leq i \leq N-1)
- 1 \leq v \leq N
- 0 \leq x, y, z < 2^{30}
- 1 \leq k \leq 10^9
- 给定的图是一棵树。 它以
入力
输入将以以下格式从标准输入给出。
N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
Q
Query_1
Query_2
:
Query_Q
- Query_i 为
1 v x k、2 v y z或3 v格式每行给出。 对于
出力
2 v y z 形式的查询,按给定顺序输出答案。
在第
入力例 1
4 1 2 1 3 3 4 14 1 1 1 1 1 2 2 1 1 3 3 1 2 1 0 4 2 2 1 3 2 4 3 2 3 4 1 3 3 1 1 4 4 1 1 1 1 1 1 2 2 1 2 1 0 4 2 2 1 3 2 4 3 2
出力例 1
1 2 2 4 5 2
- 1 个查询中, 一一添加A_1 和 A_2 和 A_3 和 A_4 有一个值 添加 1 被 1 。
- 2 个查询中, 一一添加A_2 有一个值 添加 2 被 1 添加一个。
- 3 个查询中, 一一添加A_3 和 A_4 有一个值 添加 3 被 1 。
- 4 根是顶点 1 的顶点 将其更改为 4 。
- 5 个查询中, 一一添加A_1 = \{1\} 这是 1 xor 0 = 1 所以 4 是以下值的数量: 输出 1 。
- 6 个查询中, 一一添加A_2 = \{1,2\} 这是 1 xor 1 = 0 、2 xor 1 = 3 所以 3 是以下值的数量: 输出 2 。
- 7 个查询中, 一一添加A_4 = \{1,3\} 这是 1 xor 3 = 2 、3 xor 3 = 0 所以 2 是以下值的数量: 输出 2 。
- 8 个查询中, 一一添加A_1 和 A_2 和 A_3 有一个值 添加 3 被 1 。
- 9 个查询中, 一一添加A_1 和 A_2 和 A_3 和 A_4 有一个值 添加 4 被 1 。
- 10 个查询中, 一一添加A_1 和 A_2 有一个值 添加 1 被 1 。
- 11 个查询中, 一一添加A_2 有一个值 添加 2 被 1 添加一个。
- 12 个查询中, 一一添加A_1 = \{1,3,4,1\} 这是 1 xor 0 = 1 、3 xor 0 = 3 、4 xor 0 = 4 、1 xor 0 = 1 所以 4 是以下值的数量: 输出 4 。
- 13 个查询中, 一一添加A_2 = \{1,2,3,4,1,2\} 这是 1 xor 1 = 0 、2 xor 1 = 3 、3 xor 1 = 2 、4 xor 1 = 5 、1 xor 1 = 0 、2 xor 1 = 3 所以 3 是以下值的数量: 输出 5 。
- 14 个查询中, 一一添加A_4 = \{1,3,4\} 这是 1 xor 3 = 2 、3 xor 3 = 0 、4 xor 3 = 7 所以 2 是以下值的数量: 输出 2 。
入力例 2
1 11 1 1 4 1 1 1 14 2 1 1 10 4 1 1 8 8 1 1 12 16 1 1 2 32 1 1 6 64 1 1 0 128 2 1 0 10 2 1 10 10 2 1 8 10
出力例 2
237 190 190
入力例 3
1 11 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 1 1 0 1000000000 2 1 0 2
出力例 3
10000000000
输出是 由 32 它不一定适合位整数类型。 给出
入力例 4
1 2 1 1 1 123 2 1 0 1073741823
出力例 4
123