AT_kupc2018_m 整数と根付き木

## 整数与有根树 现有一棵有根树 $T$，由顶点 $1$ 至 $N$ 编号而成。**最初的根是 $1$ 号点。** 树 $T$ 上有 $N-1$ 条边，第 $i$ 条边连接了顶点 $a_i$ 和 $b_i$。 每个顶点 $v$ 都有自己的整数数组 $A_v$。最初它们都是空的。 这棵有根树 $T$ 被查询了 $Q$ 次。共有 $3$ 种不同的查询操作，每种操作如下： - `1 v x k` \- 为顶点 $v$ 的子树中的**任意顶点（包括顶点 $v$）**$u$ 添加 $k$ 值 $x$ 至 $A_u$。 - `2 v y z` \- 求顶点 $v$ 处的数组 $A_v$ 中满足 $val$ $xor$ $y$ $\leq$ $z$ 且值为 $val$ 的元素个数。其中 $s$ $xor$ $t$ 是指 $s$ 和 $t$ 的位排中或。 - `3 v` \- 将根节点改为顶点 $v$。 您必须编写一个程序来**依次**处理这些查询。

输入通过标准输入，格式如下。 > $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： - $1$ $1$ 第二次查询将 $1$ 的值 $1$ 添加到 $A_1$ 、 $A_2$ 、 $A_3$ 和 $A_4$ 中。 - $2$ 第二次查询将 {800266674} 的值 $1$ 添加到 $A_2$ 中。 - $3$ $3$ 第二次查询将 $3$ 值 $1$ 分别添加到 $A_3$ 和 $A_4$ 中。 - $4$ $4$ 第二次查询将顶点 $1$ 的根更改为顶点 $4$ 。 - $5$ $5$ 第二次查询的结果是 $1$ ，即低于 $4$ 的值的个数，因为 $A_1 = \{1\}$ 和 $1$ $xor$ $0 = 1$ 的值都低于 $4$ 。 - $6$ 第二个查询输出 $2$ ，即 $A_2 = \{1,2\}$ 和 $1$ $xor$ $1 = 0$ 和 $2$ $xor$ $1 = 3$ ，所以 $3$ 或更少 $7$ - $7$ 第二次查询输出 $2$ ，这是低于 $2$ 的数值个数，因为 $A_4 = \{1,3\}$ 、 $1$ $xor$ $3 = 2$ 、 $3$ $xor$ $3 = 0$ 。 $2$ - $8$ 第二次查询将 $1$ 值 $3$ 添加到 $A_1$ 、 $A_2$ 和 $A_3$ 。 - 第 $9$ 次查询将 $A_1$ 和 $A_2$ 以及 $A_3$ 和 $A_4$ 的值 $4$ 添加到 $1$ 中。 - 第二个查询 $10$ 通过 $1$ 将 $1$ 的值添加到 $A_1$ 和 $A_2$ 中。 - $11$ 第二次查询通过 $1$ 将 $2$ 的值添加到 $A_2$ 中。 - $12$ $A_1 = \{1,3,4,1\}$ 查询添加了 $1$ $xor$ $0 = 1$ 、 $3$ $xor$ $0 = 3$ 、 $4$ $xor$ $0 = 4$ 、 $4$ $xor$ $0 = 4$ 、 $4$ $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$ 所以输出 $5$ ，这是低于 $3$ 的值的个数。 $5$ - $14$ ，即 $A_4 = \{1,3,4\}$ 和 $1$ $xor$ $3 = 2$ , $3$ $xor$ $3 = 0$ , $4$ $xor$ $3 = 7$ , 所以 $5$ 是 $3$ $5$ 下面的数值。 $2$ ，即低于 $2$ 的数值个数。 #### 样例3： 输出不一定适合 $32$ 位整数类型。

- 所有输入均为整数。 - $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 v \leq N$ - $0 \leq x,y,z < 2^{30}$ - $1 \leq k \leq 10^9$ - 给定图形是一棵树。