AT_iroha2019_day2_k 虫取り

※きたむー是协助出这道题的人名。另外，きたむー的女朋友并不是いろはちゃん。 今天是暑假。きたむー和他深爱的女朋友一起来捉虫。实际上，捉虫是两人加深感情非常有意义的合作活动！ きたむー发现了一棵苹果树。这棵苹果树有 $1$ 个根、$N-1$ 个叶子或节点、$N-1$ 条树枝，结构与信息科学中的树结构非常相似。叶子、节点以及根在下文中统称为顶点。根的编号为 $0$，其余每个顶点编号为 $1\sim N-1$。一开始，きたむー在根上。 这棵苹果树上会结出美味的果实，因此顶点上会有すぬけ虫前来。すぬけ虫以群体生活，非常聪明，某个顶点为根的子树中，每个顶点都会均匀分布すぬけ虫。例如，若一个有 $3$ 个顶点的子树来了 $15$ 只すぬけ虫，则每个顶点上会有 $5$ 只。注意，すぬけ虫只会来到虫的数量能被子树顶点数整除的子树。初始时，每个顶点上的すぬけ虫数量为 $0$。 这棵树非常高大，用捕虫网根本够不到，所以きたむー决定在顶点间移动来捕捉すぬけ虫。不过，如果每次都要下树确认虫的位置会很浪费时间，因此他会根据女朋友的 $Q$ 次指示，在顶点间移动。 指示有以下两种类型： 指示 $A$ 形式如下： > $0\ i\ k$ 表示以第 $i$ 个顶点为根的子树来了 $k$ 只すぬけ虫。 指示 $B$ 形式如下： > $1\ i$ 此时，きたむー会从当前所在顶点，沿最短路径移动到第 $i$ 个顶点。途中经过的所有顶点（包括起点和终点）上的すぬけ虫都会被捕获，并将捕获的总数报告给女朋友。之后，きたむー会一直停留在顶点 $i$，直到下一个 $B$ 指令。 捕虫试炼，考验两人的爱情，现在开始……

输入按以下格式从标准输入给出。 > $N$ $Q$ $C_1$ $D_1$ $C_2$ $D_2$ $\cdots$ $C_{N-1}$ $D_{N-1}$ 指令1 指令2 $\cdots$ 指令Q 其中，整数 $C_i,\ D_i$ 表示第 $i$ 条树枝连接了顶点 $C_i$ 和 $D_i$。

每当收到指示 $B$ 时，输出捕获到的すぬけ虫总数。

## 约束 - 所有输入均为整数。 - $1\leq N\leq 2\times 10^5$ - $1\leq Q\leq 8\times 10^4$ - $0\leq C_j, D_j\leq N-1\ (1\leq j\leq N-1)$ - 输入的图保证是一棵树。 - $0\leq i\leq N-1$ - $0\leq k\leq 10^9$ - $k$ 能被以顶点 $i$ 为根的子树的顶点数整除。 ## 部分分 - 若能通过以下输入输出样例可得 $1$ 分。 - 若能通过所有测试点，可再得 $1199$ 分。 ## 实现注意事项 - 本题为**交互题**。每次收到 $B$ 指令并输出捕获虫数后，才会收到下一个指令，请注意。 - 输出后必须刷新标准输出，否则可能会 `TLE`。 - 输出答案后，程序应立即结束，否则行为未定义。 - 若输出答案错误，行为未定义（不一定是 `WA`）。 ## 解说 [解说](https://img.atcoder.jp/iroha2019-day2/editorial-K.pdf) ## 样例说明 2 请注意，实际上只有在输出了 $B$ 指令的答案后，才会收到下一个指令。 由 ChatGPT 4.1 翻译