1092: 魔女中的魔女

最近 LinXce 迷上了 《魔女之泉2077》，游戏中聪明可爱的小魔女琳科斯十分擅长时间魔法。

这一天，琳科斯遇到了麻烦：在树形结构的道路上出现了许多刷怪笼，怪兽会不定时的从刷怪笼中出现。

琳科斯可以选择一条路径，用探测魔法感知到路径上一共有多少只怪兽。

为了避免遇到太多怪兽，琳科斯还可以选择一条路径，并回溯道路上的时间，这样道路上的怪兽就没有那么多了。

正式的说：

在一棵有 $n$ 个节点的树上，出现了 $m$ 次事件（一开始树上什么也没有）

每一秒会发生以下三个事件中的一个（假定当前时间为第 $k$ 秒）：

• 事件1：节点 $u$ 上增加了 $x$ 只怪兽。
• 事件2：琳科斯询问从 $u$ 到 $v$ 的简单路径上有一共多少只怪兽。
• 事件3：琳科斯回溯从 $u$ 到 $v$ 的简单路径的时间到第 $s$ 秒时的状态（$0 < s < k$）

注：从第 $1$ 秒开始发生事件（包括第 $1$ 秒），此外，每发生一次事件（对于事件2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。第 $k$ 秒发生的事件对应的版本编号即为版本 $k$。

第 $1$ 行输入两个整数 $n、m$ （$1 \leq n、m \leq10^5$）

接下来 $n - 1$ 行，每行输入两个整数 $u$、$v$，表示点 $u$ 和点 $v$ 之间连有一条边（$1 \leq u、v \leq n$）

接下来 $m$ 行，每行包含 3 到 4 个整数，表示一个事件，具体如下：

• $1\space u\space x$ 节点 $u$ 上增加了 $x$ 只怪兽（$1 \leq u \leq n、1 \leq x \leq 10^9$）
• $2\space u\space v$ 询问从 $u$ 到 $v$ 的简单路径上一共多少只怪兽（$1 \leq u、v \leq n$）
• $3\space u\space v \space s$ 将从 $u$ 到 $v$ 的简单路径上的节点还原为第 $s$ 号版本（保证 $s$ 合法）

4 6
1 2
2 3
3 4
1 1 1
1 2 2
1 4 1
2 1 3
3 1 2 1
2 1 4

3
2