← 返回题目列表

AtCoder · kupc2018_m

M. 整数和有根树

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

配点 : 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