题目描述

给定一棵 $n$ 个节点的树，钦定点 $1$ 为根，每条边的边权均为 $1$ ，节点 $x$ 有点权 $a_x$ ，初始所有节点的点权均为 $0$ 。总共有 $m$ 次操作，每次操作先给出操作类型 $\text{opt}$ ，接下来给出该操作的所有参数。

1. 给定一条路径 $(x, y)$ 和范围 $k$ 以及权值 $u$，对于所有点 $i$，当点 $i$ 满足其到树上路径 $(x, y)$ 的最短距离 $\le k$ 时，有 $a_i \gets a_i + u$。
2. 给定点 $x$ 以及权值 $u$，对于所有点 $x$ 子树内的节点 $i$，有 $a_i \gets a_i + u$。
3. 给定一条路径 $(x, y)$ 和范围 $k$，对于所有点 $i$，当点 $i$ 满足其到树上路径 $(x, y)$ 的最短距离 $\le k$ 时，询问所有这样的点 $i$ 的点权和。
4. 给定点 $x$，对于所有点 $x$ 子树内的节点 $i$，询问所有这样的点 $i$ 的点权和。
5. 给定一条路径 $(x, y)$ 和范围 $k$，对于所有点 $i$，当点 $i$ 满足其到树上路径 $(x, y)$ 的最短距离 $\le k$ 时，询问所有这样的点 $i$ 的点权最大值。
6. 给定点 $x$，对于所有点 $x$ 子树内的节点 $i$，询问所有这样的点 $i$ 的点权最大值。

其中编号对应操作类型，操作的所有参数将以上述描述的变量顺序给出。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$，表示树的大小和操作数量。

接下来的第 $2$ 行到第 $n$ 行每行两个正整数 $u, v$ 表示树的一条边 $(u, v)$。

接下来 $m$ 行，每一行首先输入一个整数 $\text{opt}$，表示操作类型：

• 若 $\text{opt} = 1$，接下来继续输入 $x, y, k, u$；
• 若 $\text{opt} = 2$，接下来继续输入 $x, u$；
• 若 $\text{opt} = 3$，接下来继续输入 $x, y, k$；
• 若 $\text{opt} = 4$，接下来继续输入 $x$；
• 若 $\text{opt} = 5$，接下来继续输入 $x, y, k$；
• 若 $\text{opt} = 6$，接下来继续输入 $x$。

输出格式

输出若干行，对于每一种操作三、操作四、操作五、操作六，输出对应的答案。

数据范围

本题开启子任务评测，子任务之间将会设置合理的依赖关系。

• 子任务 $1$ 和 子任务 $2$ ($10$ 分 + $10$ 分): 保证 $k = 0$ 。
• 子任务 $3$ 和 子任务 $4$ ($10$ 分 + $10$ 分): 保证所有涉及路径 $(x, y)$ 的操作满足 $x = y$ 。
• 子任务 $5$ 和 子任务 $6$ ($10$ 分 + $10$ 分): 保证 $k = 1$ 。
• 子任务 $7$ 和 子任务 $8$ ($20$ 分 + $20$ 分): 无特殊限制。

上述子任务中所有奇数编号子任务不包含操作五和操作六。

对于所有数据，保证 $1 \le n, m \le 2 \times 10^5$，$0 \le k \le 3$，$-10^5 \le u \le 10^5$。