AT_kupc2019_l.タケノコ

这是一个交互式问题。

有一棵起始只有一个节点的有根树 $T$，这个节点编号为 $0$。在顶点 $0$ 上生长着一根长度为 $x_0$ 且生长速度为 $y_0$ 的竹笋。

此外，还有一个叫“竹痴君”的人在顶点 $0$。

你需要依次处理 $Q$ 个查询。查询分为以下三种类型：

1. 查询 1: 1 v x y —— 以顶点 $v$ 为父节点，添加一个新顶点，该新顶点上生长一根长度为 $x$ 且生长速度为 $y$ 的竹笋。新顶点编号为上一个添加的顶点编号加 $1$（如果没有添加过则为 $0$）。

2. 查询 2: 2 a —— 竹痴君在整棵树 $T$ 上洒下效果为 $a$ 的肥料，导致任意顶点的竹笋，若当前长度为 $x$ 且生长速度为 $y$，其长度变化为 $x + a \times y$。

3. 查询 3: 3 v —— 询问竹痴君从根到顶点 $v$ 的路径上（包含起点和终点）的可见竹笋有多少。竹痴君能精确数出不超过 30 根的竹笋，超过 30 根则回答为 many。你需要给出他的回答。

竹痴君能看到某根竹笋 $t$ 意味着从顶点 $0$ 到竹笋 $t$ 所在顶点的路径上所有节点的竹笋高度依次为 $h_1, h_2, \ldots, h_n$ 时，满足 $h_i < h_n$（$1 \leq i \leq n - 1$）。竹痴君总能看到顶点 $0$ 上的竹笋。

输入从标准输入读取，格式如下：

$ Q $ $ x_0 $ $ y_0 $ $ Query_1 $ $ Query_2 $ $ \ldots $ $ Query_Q $

查询 $Query_i$ ($1 \leq i \leq Q$) 按上述三种类型之一给出。

对于每个查询 3，输出你预测的答案。

• $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$
• 所有输入均为整数。

输入输出注意事项

• 这是一个 交互式问题。只有在每个查询 3 后输出答案才能继续接收后续输入。
• 输出的最后一行必须包括一个换行符，并刷新标准输出，否则可能会遇到 TLE。
• 如果输出格式有误，行为未定义（可能不返回 WA）。
• 由于交互特性，无论语言是什么，在最坏情况下输入输出至少需要约 $4$ 秒。请注意时间限制。

示例说明

• 对于第一个查询，以顶点 $0$ 为父节点，添加了编号为 $1$ 的新顶点，该顶点上的竹笋高度为 $2$，生长速度为 $2$。
• 在第二个查询中，竹痴君数了顶点 $0$ 和 $1$ 上可见的竹笋。顶点 $0$ 和 $1$ 上的竹笋高度分别为 $1$ 和 $2$，竹痴君可见这两根竹笋，因此结果是 $2$。
• 第三个查询，将顶点 $0$ 和 $1$ 上的竹笋高度变为 $-1$ 和 $-2$。竹笋高度可以为负。
• 第四个查询，竹痴君寻找顶点 $0$ 和 $1$ 上可见的竹笋，此时顶点 $1$ 上的竹笋不符合条件，无法观察，因此结果为 $1$。请注意，即使竹笋高度为负，其可见性仍旧按照题目所述处理。

本翻译由 AI 自动生成