配点: 1200 点
这是一个交互问题。
我们建议您用快速语言回答此问题。已确认 AC 可以与 C++14 (GCC 5.4.1) 一起使用。
問題文
*Kitamu 是帮助编写此问题的人的名字。而且,Kitamu的女朋友不是伊吕波。
今天是暑假。北木和他心爱的女朋友一起来捉虫子。事实上,抓虫子是一项非常有意义的协作活动,可以加深两个人之间的感情!
北木哈1我发现了一本书苹果树。这棵苹果树 1 根,N-1 叶子或节点, N-1 它由一本书的分支组成,与信息科学中的树结构非常相似。叶或节点和根在下文中被称为顶点。根数 0 但每个顶点都有一个数字 1 \sim N-1 正在挥舞。起初,Kitamu 是根源。
这棵苹果树结出美味的果实,斯努克昆虫也来到了顶端。蛇甲虫群居,非常聪明,分散栖息在以某个顶点为根的子树的各个顶点上。例如,顶点数 在 3 的子树中 15 当斯努克虫子来的时候, 5 它们分成几组并停在每个顶点。请注意,snook bug 不会出现在群中 bug 数量不能被顶点数量整除的子树中。此外,最初栖息在每个顶点的斯诺克昆虫是 0 。
这棵树太高了,很难用捕虫网到达,所以 Kitamuu 决定在树顶之间移动并捕捉斯努克虫。不过,爬下树去查看斯诺克昆虫的下落实在是浪费时间,所以我让她 Q 收到指示后,我决定在顶点之间移动。
说明如下 2 由类型组成。 它以
指示 A 表示
0 i k
的形式给出。这是 以第i 个顶点为根的子树 k 这意味着一群斯努克虫已经到来。 它以
指示 B 表示
1 i
的形式给出。此时,Kitamu 将从他目前所在的位置上移走 使用最短路径移动到第 i 个顶点。那时,捕捉你旅途中所经过的顶点,包括起点和终点的所有虫子,并将总数报告给她。之后,Kitamu给出了以下指示。 直到 B 为止的顶点 留在 i 。
考验两人爱情的捉虫审判现在开始……
制約
- 输入全为整数。
- 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 点。
入力
输入将以以下格式从标准输入提供。
N Q
C_1 D_1
C_2 D_2
\vdots
C_{N-1} D_{N-1}
指示1
指示2
\vdots
指示Q
其中整数 C_i,\ D_i 是 N-1 分支机构之中 i 第一个分支是顶点 这意味着连接 C_i 和 D_i 。 对于给出的每个
出力
指示 B ,报告您捕获的斯努克虫总数。
实施说明
- 这个问题是 互动问题 。说明 请注意,除非您在给出 B 后报告您捕获的斯努克错误的数量,否则您将不会收到下一条指令。
- 打印后,必须刷新标准输出。当它不是
有一种可能性是
TLE。 - 程序必须在打印答案后立即退出。否则行为是未定义的。
- 输出答案错误时的行为未定义(
WA)。
入力例 1
6 4 0 3 3 1 3 2 4 5 0 5 0 3 9 0 1 2 0 2 5 1 1
出力例 1
8
入力例 2
9 9 0 5 0 2 0 1 5 8 5 7 5 4 2 3 2 6 0 0 9 0 2 6 0 8 4 1 8 1 1 0 3 8 0 0 144 0 3 32 1 3
出力例 2
7 1 110
实际说明 请注意,除非在 B 之后输出答案,否则无法给出下一条指令。