← 返回题目列表

AtCoder · kupc2019_l

L. 竹笋

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

配点 : 500 点

問題文

这是一个互动问题。

1 两个顶点的有根树 有 T ,这个顶点就是顶点 比方说 0 。顶点 0 的长度 x_0 使其更容易拉伸。 y_0 竹笋正在生长。

另外,顶点 0 有水叶君。 您将收到

Q 查询,因此请按顺序处理。查询是 3 有多种类型,其格式如下。

  • 查询 1 : 1 v x y ― 頂点 v 添加一个带有 x 使其更容易拉伸。 y 竹笋的新顶点。新的顶点编号是之前添加的顶点编号(如果不是, 0 ) + 1 。
  • 查询 2 : 2 a - 水叶君是一棵有根的树 T 对整体的影响 撒施 a 肥料。这使得有根树能够 生长在 T 任意顶点的竹笋当前长度为 x 使其更容易拉伸。 y 那么长度是 更改为 x + a \times y 。
  • 查询 3 : 3 v - 水叶君的上衣 询问通往 v 的简单路径(包括两端)上可见的竹笋数量。你这个白痴 30 你可以准确地数出并回答比一本书还小的竹笋数量,但是31 数一本书以上就变得很麻烦。 many 就是答案。请预测这个答案并打印出来。

不过,水叶君有竹笋。 如果 t 可见,则表示顶点 来自 0 的竹笋 简单路径上的顶点(包括两端)到 t 生长的顶点的竹笋高度按顺序确定。 当 h_1, h_2, ..., h_n 时,h_i < h_n (1 \leq i \leq n - 1) 。另外,水叶君也位居榜首。 你可以看到 0 竹笋。

制約

  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq x_0 \leq 10^9
  • 1 \leq y_0 \leq 10^6
  • 0 \leq v \leq (最后添加的顶点编号(如果不是 0 ))
  • 1 \leq x \leq 10^9
  • 1 \leq y \leq 10^6
  • -10^6 \leq a \leq 10^6
  • 查询 3 的数量是 不超过 3 \times 10^4 。
  • 所有输入均为整数。

入力

输入是按以下格式从标准输入给出的。

Q x_0 y_0
Query_1
Query_2
:
Query_Q

Query_i(1 \leq i \leq Q) 在问题文本中 3 可以采用以下格式之一给出: 打印每个

出力

查询 3 的答案。

输入/输出注意事项

  • 这个问题是 互动问题 。查询 除非您输出每个 3 的答案,否则不会给出进一步的输入。
  • 输出末尾必须包含换行符。之后,您需要刷新标准输出。当它不是 可能是 TLE 。
  • 输出格式错误时的行为未定义。 (WA 情况不一定如此。 )
  • 在这个问题中,出于交互原因,输入/输出至少是 4 大约需要秒,所以要注意执行时间限制。

入力例 1

4 1 1
1 0 2 2
3 1
2 -2
3 1

出力例 1

2
1
  • 1 在第二个查询中,顶点 父级为 0 的顶点 添加了 1 。顶点 1 竹笋的高度是 使用 2 轻松拉伸 2 。
  • 2 在第二个查询中,顶点 父级为 0, 1 数一下你能从竹笋中看到的东西。顶点 0, 1 每个竹笋的高度是 1, 2 和Suibaka都可以看到竹笋。所以答案是 2 。
  • 3 在第二个查询中,顶点 父级为 0, 1 每个竹笋的高度是 -1, -2 。这样,竹笋的高度也可以为负值。
  • 4 在第二个查询中,顶点 父级为 0, 1 数一下你能从竹笋中看到的东西。此时,顶点 1 的竹笋是 0 竹笋高度) < (頂点 1 竹笋的高度)不满足,所以不可见。所以答案是 1 。请注意,即使竹笋的高度为负,它在水叶君看来的样子也如问题文本中所写。

入力例 2

12 1 1
1 0 5 1
1 1 2 3
2 1
3 2
1 2 1 5
2 2
3 3
1 2 1 1
2 -4
3 3
2 5
3 4

出力例 2

2
3
2
3

入力例 3

34 1 1
1 0 1 2
1 1 1 3
1 2 1 4
1 3 1 5
1 4 1 6
1 5 1 7
1 6 1 8
1 7 1 9
1 8 1 10
1 9 1 11
1 10 1 12
1 11 1 13
1 12 1 14
1 13 1 15
1 14 1 16
1 15 1 17
1 16 1 18
1 17 1 19
1 18 1 20
1 19 1 21
1 20 1 22
1 21 1 23
1 22 1 24
1 23 1 25
1 24 1 26
1 25 1 27
1 26 1 28
1 27 1 29
1 28 1 30
1 29 1 31
3 30
2 1
3 29
3 30

出力例 3

1
30
many