Gold Transfer

题意翻译

本题强制在线，请在**处理完每次询问之后**再继续读入数据，同时也请注意刷新缓冲区。 给定一个初始只有一个根节点（编号为 $0$）的有根树，第 $i$ 个节点有 $a_i$ 块金子，在该节点上每块金子价格均为 $c_i$。 你需要维护这棵树，处理 $q$ 次操作，操作有两种，具体的： 1. 假设这是第 $i$ 次操作，给定整数 $p_i,a_i,c_i$。你需要创建一个节点 $i$ 使得节点 $p_i$ 是节点 $i$ 的父节点，且拥有 $a_i$ 块金子，每块有价格 $c_i$。**我们保证 $c_i>c_{p_i}$ 成立。** 2. 给定整数 $v_i,w_i$，你需要从节点 $v_i$ 到节点 $0$ 的所有节点上买正好 $w_i$ 块金子，且总价格最小。输出买到的金子数和最小总价格。**注意，如果路径中没有足够金子的话，你需要买下路径上的所有金子。** $1\leq q\leq3\times10^5;1\leq a_0,c_0<10^6;$ 对于操作一：$0\leq p_i<i;1\leq a_i,c_i<10^6;c_i>c_{p_i};$ 对于操作二：$0\leq v_i<i;1\leq w_i<10^6;$ 且节点 $v_i$ 一定存在。 我们还保证，一定至少有一次操作二。

题目描述

You are given a rooted tree. Each vertex contains $ a_i $ tons of gold, which costs $ c_i $ per one ton. Initially, the tree consists only a root numbered $ 0 $ with $ a_0 $ tons of gold and price $ c_0 $ per ton. There are $ q $ queries. Each query has one of two types: 1. Add vertex $ i $ (where $ i $ is an index of query) as a son to some vertex $ p_i $ ; vertex $ i $ will have $ a_i $ tons of gold with $ c_i $ per ton. It's guaranteed that $ c_i > c_{p_i} $ . 2. For a given vertex $ v_i $ consider the simple path from $ v_i $ to the root. We need to purchase $ w_i $ tons of gold from vertices on this path, spending the minimum amount of money. If there isn't enough gold on the path, we buy all we can. If we buy $ x $ tons of gold in some vertex $ v $ the remaining amount of gold in it decreases by $ x $ (of course, we can't buy more gold that vertex has at the moment). For each query of the second type, calculate the resulting amount of gold we bought and the amount of money we should spend. Note that you should solve the problem in online mode. It means that you can't read the whole input at once. You can read each query only after writing the answer for the last query, so don't forget to flush output after printing answers. You can use functions like fflush(stdout) in C++ and BufferedWriter.flush in Java or similar after each writing in your program. In standard (if you don't tweak I/O), endl flushes cout in C++ and System.out.println in Java (or println in Kotlin) makes automatic flush as well.

输入输出格式

输入格式

The first line contains three integers $ q $ , $ a_0 $ and $ c_0 $ ( $ 1 \le q \le 3 \cdot 10^5 $ ; $ 1 \le a_0, c_0 < 10^6 $ ) — the number of queries, the amount of gold in the root and its price. Next $ q $ lines contain descriptions of queries; The $ i $ -th query has one of two types: - " $ 1 $ $ p_i $ $ a_i $ $ c_i $ " ( $ 0 \le p_i < i $ ; $ 1 \le a_i, c_i < 10^6 $ ): add vertex $ i $ as a son to vertex $ p_i $ . The vertex $ i $ will have $ a_i $ tons of gold with price $ c_i $ per one ton. It's guaranteed that $ p_i $ exists and $ c_i > c_{p_i} $ . - " $ 2 $ $ v_i $ $ w_i $ " ( $ 0 \le v_i < i $ ; $ 1 \le w_i < 10^6 $ ): buy $ w_i $ tons of gold from vertices on path from $ v_i $ to $ 0 $ spending the minimum amount of money. If there isn't enough gold, we buy as much as we can. It's guaranteed that vertex $ v_i $ exist. It's guaranteed that there is at least one query of the second type.

输出格式

For each query of the second type, print the resulting amount of gold we bought and the minimum amount of money we should spend.

输入输出样例

输入样例 #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

说明

Explanation of the sample: At the first query, the tree consist of root, so we purchase $ 2 $ tons of gold and pay $ 2 \cdot 2 = 4 $ . $ 3 $ tons remain in the root. At the second query, we add vertex $ 2 $ as a son of vertex $ 0 $ . Vertex $ 2 $ now has $ 3 $ tons of gold with price $ 4 $ per one ton. At the third query, a path from $ 2 $ to $ 0 $ consists of only vertices $ 0 $ and $ 2 $ and since $ c_0 < c_2 $ we buy $ 3 $ remaining tons of gold in vertex $ 0 $ and $ 1 $ ton in vertex $ 2 $ . So we bought $ 3 + 1 = 4 $ tons and paid $ 3 \cdot 2 + 1 \cdot 4 = 10 $ . Now, in vertex $ 0 $ no gold left and $ 2 $ tons of gold remain in vertex $ 2 $ . At the fourth query, we add vertex $ 4 $ as a son of vertex $ 0 $ . Vertex $ 4 $ now has $ 1 $ ton of gold with price $ 3 $ . At the fifth query, a path from $ 4 $ to $ 0 $ consists of only vertices $ 0 $ and $ 4 $ . But since no gold left in vertex $ 0 $ and only $ 1 $ ton is in vertex $ 4 $ , we buy $ 1 $ ton of gold in vertex $ 4 $ and spend $ 1 \cdot 3 = 3 $ . Now, in vertex $ 4 $ no gold left.