CF1535E Gold Transfer

给定一棵有根树，每个顶点包含 $a_i$ 吨黄金，每吨黄金的价格为 $c_i$。初始时，树中只有编号为 $0$ 的根节点，拥有 $a_0$ 吨黄金，每吨价格为 $c_0$。 共有 $q$ 个操作。每个操作有两种类型： 1. 将顶点 $i$（其中 $i$ 为当前操作的编号）作为某个顶点 $p_i$ 的儿子加入树中；顶点 $i$ 拥有 $a_i$ 吨黄金，每吨价格为 $c_i$。保证 $c_i > c_{p_i}$。 2. 对于给定的顶点 $v_i$，考虑从 $v_i$ 到根节点的简单路径。你需要从路径上的顶点购买 $w_i$ 吨黄金，使得花费最少。如果路径上的黄金不足，则尽可能多地购买。 如果在某个顶点 $v$ 购买了 $x$ 吨黄金，则该顶点剩余的黄金数量减少 $x$（当然，不能购买超过当前剩余的黄金数量）。对于每个第二类操作，输出实际购买的黄金数量以及所需花费。 注意：你需要以在线方式解决本题。这意味着你不能一次性读入全部输入。你只能在输出上一个操作的答案后，才能读取下一个操作。因此，输出答案后不要忘记刷新输出缓冲区。你可以在 C++ 中使用 fflush(stdout)，在 Java 中使用 BufferedWriter.flush 或类似方法。在标准情况下（如果不调整 I/O），C++ 的 endl 会刷新 cout，Java 的 System.out.println（或 Kotlin 的 println）也会自动刷新。

第一行包含三个整数 $q$、$a_0$ 和 $c_0$（$1 \leq q \leq 3 \cdot 10^5$；$1 \leq a_0, c_0 < 10^6$），分别表示操作数、根节点的黄金数量和每吨黄金的价格。 接下来的 $q$ 行描述每个操作，第 $i$ 行有以下两种格式之一： - “$1\ p_i\ a_i\ c_i$” （$0 \leq p_i < i$；$1 \leq a_i, c_i < 10^6$）：将顶点 $i$ 作为顶点 $p_i$ 的儿子加入树中。顶点 $i$ 拥有 $a_i$ 吨黄金，每吨价格为 $c_i$。保证 $p_i$ 存在且 $c_i > c_{p_i}$。 - “$2\ v_i\ w_i$” （$0 \leq v_i < i$；$1 \leq w_i < 10^6$）：从 $v_i$ 到 $0$ 的路径上购买 $w_i$ 吨黄金，使花费最小。如果黄金不足，则尽量多买。保证 $v_i$ 存在。 保证至少有一个第二类操作。

对于每个第二类操作，输出实际购买的黄金数量和所需的最小花费。

样例解释： 第一次操作时，树中只有根节点，因此我们购买 $2$ 吨黄金，花费 $2 \times 2 = 4$。根节点剩余 $3$ 吨黄金。 第二次操作，将顶点 $2$ 作为 $0$ 的儿子加入。顶点 $2$ 现在有 $3$ 吨黄金，每吨价格为 $4$。 第三次操作，从 $2$ 到 $0$ 的路径包含顶点 $0$ 和 $2$，由于 $c_0 < c_2$，我们先在顶点 $0$ 购买剩余的 $3$ 吨黄金，再在顶点 $2$ 购买 $1$ 吨。共买了 $3+1=4$ 吨，花费 $3 \times 2 + 1 \times 4 = 10$。此时顶点 $0$ 没有黄金，顶点 $2$ 剩余 $2$ 吨黄金。 第四次操作，将顶点 $4$ 作为 $0$ 的儿子加入。顶点 $4$ 现在有 $1$ 吨黄金，每吨价格为 $3$。 第五次操作，从 $4$ 到 $0$ 的路径包含顶点 $0$ 和 $4$。但顶点 $0$ 没有黄金，顶点 $4$ 只有 $1$ 吨黄金，因此我们在顶点 $4$ 购买 $1$ 吨黄金，花费 $1 \times 3 = 3$。此时顶点 $4$ 没有黄金。 由 ChatGPT 4.1 翻译