魔法森林 - 题目

魔法森林（Forest of Magic），顾名思义，是一片充满魔法的森林。雾雨魔理沙（Kirisame Marisa）是一位年轻但技艺高超的魔法使，她就居住在这片森林中。

森林中有许多地点，它们通过双向道路连接，使得任意两个地点之间都可以直接或间接地通过道路到达，且从一个地点到另一个地点只有唯一的一条简单路径。换句话说，森林中的地点和道路构成了一棵树。

最初，森林中有 $n$ 个地点，编号从 $1$ 到 $n$。魔理沙的家位于 $1$ 号地点，因此从魔理沙的角度来看，森林可以被视为一棵以 $1$ 为根的树。

由于所有丢失的东西最终都会流向幻想乡，森林中会不时出现新的地点。新地点会与一个现有的地点通过一条双向道路连接，因此在出现新地点后，森林依然保持为一棵树。

森林里还有许多淘气的妖精。有时，一只妖精会从一个特定的地点前往另一个地点。由于妖精是自然的化身，在妖精经过的每一个地点上，都会长出 $k$ 朵特定颜色的花。颜色可以用 $1$ 到 $10^9$ 之间的数字表示。

魔理沙很喜欢花，有时她想邀请朋友们一起赏花。在此之前，她会统计特定地点的子树中，颜色编号不大于 $c$ 的花的数量总和。如果 $u$ 位于 $v$ 到 $1$ 的简单路径上，我们就称地点 $v$ 在 $u$ 的子树中。注意，魔理沙不会采摘这些花，因此统计操作不会改变任何东西。

然而，森林太大了，所以她每次都要求你进行统计。此外，你必须在她每次询问时立即给出回答。

输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 3 \times 10^4$, $0 \le q \le 10^5$)，表示森林中最初有 $n$ 个地点，魔理沙将进行 $q$ 次操作。

接下来的 $n - 1$ 行，每行包含两个正整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，由空格分隔，表示在 $u_i$ 号地点和 $v_i$ 号地点之间有一条直接连接的双向道路。

接下来的 $q$ 行，每行按顺序表示一个操作，格式为以下三种之一：

$1 \ u_i$：出现了一个新地点，编号为 $n' + 1$，其中 $n'$ 表示该操作前地点的总数。此外，新地点与 $u_i$ 号地点 ($1 \le u_i \le n'$) 之间有一条道路。
$2 \ u_i \ v_i \ c_i \ k_i$：一只妖精从 $u_i$ 号地点前往 $v_i$ 号地点，在它们之间唯一简单路径上的每个地点（包括两个端点）上，都会长出 $k_i$ ($1 \le k_i \le 10^7$) 朵颜色为 $c_i$ ($1 \le c_i \le 10^9$) 的花。保证 $u_i$ 号地点和 $v_i$ 号地点均已存在。
$3 \ u_i \ c_i$：魔理沙想知道 $u_i$ 号地点的子树中，颜色编号不大于 $c_i$ ($1 \le c_i \le 10^9$) 的花有多少朵。子树的定义已在题目描述中给出。

此外，为了确保你能立即回答魔理沙的询问，你需要维护一个变量 last，它等于上一次询问的答案对 $2^{31}$ 取模的结果（初始为 $0$）。每次读取一行操作时，除第一个数字外，所有数字都应与 last 进行按位异或（bitwise XOR）运算，运算结果即为该数字的实际值。

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下： * 当 $A \oplus B$ 写成二进制时，若 $A$ 和 $B$ 在 $2^k$ 位 ($k \ge 0$) 上的数字恰好有一个为 $1$，则结果在该位上为 $1$，否则为 $0$。

保证： 输入中的每个数字都是小于 $2^{31}$ 的非负整数。 使用上述方法还原后，数字的实际值满足上述限制。 地点总数不超过 $5 \times 10^4$。 第二类操作的总次数不超过 $5 \times 10^4$。

对于每个第三类操作，输出一行一个非负整数，表示 $u_i$ 号地点的子树中颜色不大于 $c_i$ 的花的数量。

3 5
1 2
1 3
2 2 3 1 4
3 1 1
1 13
2 13 8 14 13
3 13 14

12
14

输入中数字的实际值应为：

QOJ.ac