← 返回题目列表

AtCoder · iroha2019_day2_k

K. 驱虫剂

中文机器翻译题面 查看原题

配点: 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 之后输出答案,否则无法给出下一条指令。


解説

解説