← 返回题目列表

Codeforces · 1535/E

E. 黄金转账

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

你得到了一棵有根的树。每个顶点包含 $$$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),endl 会刷新 C++ 中的 cout,Java 中的 System.out.println(或 Kotlin 中的 println)也会自动刷新。

输入

第一行包含三个整数 $$$q$$$、$$$a_0$$$ 和 $$$c_0$$$ ($$$1 \le q \le 3 \cdot 10^5$$$; $$$1 \le a_0, c_0 < 10^6$$$) — 查询数量、根中的黄金数量及其价格。

接下来的 $$$q$$$ 行包含查询的描述;第 $$$i$$$ 查询具有以下两种类型之一:

- "$$$1$$$ $$$p_i$$$ $$$a_i$$$ $$$c_i$$$" ($$$0 \le p_i < i$$$; $$$1 \le 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 \le v_i < i$$$; $$$1 \le w_i < 10^6$$$): 从 $$$v_i$$$ 到 $$$0$$$ 的路径上的顶点购买 $$$w_i$$$ 吨黄金,花费最低金额钱。如果没有足够的黄金,我们就尽可能多地购买。保证顶点 $$$v_i$$$ 存在。

保证至少有一个第二类型的查询。

输出

对于第二类的每个查询,打印我们购买的黄金数量以及我们应该花费的最低金额。

示例

输入 #1

5 5 2
2 0 2
1 0 3 4
2 2 4
1 0 1 3
2 4 2

输出 #1

2 4
4 10
1 3

注意

样本说明:

在第一次查询时,树由根组成,因此我们购买 $$$2$$$ 吨黄金并支付 $$$2 \cdot 2 = 4$$$。 $$$3$$$ 吨仍留在根部。

在第二个查询中,我们添加顶点 $$$2$$$ 作为顶点 $$$0$$$ 的儿子。 Vertex 现在 $$$2$$$ 拥有 $$$3$$$ 吨黄金,价格为每吨 $$$4$$$。

在第三个查询中,从 $$$2$$$ 到 $$$0$$$ 的路径仅由顶点 $$$0$$$ 和 $$$2$$$ 组成,并且由于 $$$c_0 < c_2$$$,我们在顶点 $$$0$$$ 中购买剩余的 $$$3$$$ 吨黄金,在顶点 $$$2$$$ 中购买 $$$1$$$ 吨黄金。因此,我们购买了 $$$3 + 1 = 4$$$ 吨并支付了 $$$3 \cdot 2 + 1 \cdot 4 = 10$$$。现在,在顶点 $$$0$$$ 中没有剩下黄金,并且在顶点 $$$2$$$ 中保留了 $$$2$$$ 吨黄金。

在第四个查询中,我们添加顶点 $$$4$$$ 作为顶点 $$$0$$$ 的儿子。 Vertex $$$4$$$ 现在拥有 $$$1$$$ 吨黄金,价格为 $$$3$$$。

在第五个查询中,从 $$$4$$$ 到 $$$0$$$ 的路径仅包含顶点 $$$0$$$ 和 $$$4$$$。但由于顶点 $$$0$$$ 中没有剩下黄金,并且顶点 $$$4$$$ 中只有 $$$1$$$ 吨,因此我们在顶点 $$$4$$$ 中购买 $$$1$$$ 吨黄金,并花费 $$$1 \cdot 3 = 3$$$。现在,在顶点 $$$4$$$ 中没有剩下金子了。