SP17732 SALMAN - Salary Management
题目描述
**工资管理**
你是一名 Moogle 公司的软件工程师，老板希望你开发一个程序，用于有效地处理公司员工的薪资管理。首先，我们需要了解公司的员工结构。每位员工都有一个编号，编号范围从 1 到 $N$。编号为 1 的员工是总经理，是所有员工的最高领导者。除了总经理，每位员工都有一个直接上司，并且没有员工拥有多个直接上司。现在老板希望程序能够执行以下操作：
1. 给定一个员工编号，计算该员工及其所有下属（包含其自身）的工资总和。
2. 给定一个员工编号，将该员工及其所有下属的工资（包含其自身）增加。这次增加的金额为这些员工中的最低工资与 1000 之间的较小值。
举例说明：
考虑如下结构图：
假设工资表如下：
| 编号 | 工资 (BDT) |
|------|------------|
| 1 | 500 |
| 2 | 300 |
| 3 | 200 |
| 4 | 100 |
| 5 | 10 |
| 6 | 200 |
| 7 | 100 |
如果老板要求对编号为 2 的员工执行第一种操作，则输出结果为：
300 + 100 + 200 = 600 BDT
如果老板要求对编号为 1 的员工执行第二种操作，则工资表将变为：
| 编号 | 工资 (BDT) |
|------|------------|
| 1 | 510 |
| 2 | 310 |
| 3 | 210 |
| 4 | 110 |
| 5 | 20 |
| 6 | 210 |
| 7 | 110 |
因为编号为 5 的员工最低工资为 10，小于 1000，因此增加 10。
输入格式
输入的第一行为一个整数 $T$，表示测试用例的数量。
每个测试用例的第一行是一个空行。接下来的一行包含两个整数 $N$ 和 $q$，分别表示员工总数和查询次数。员工编号从 1 到 $N$。
随后有 $N$ 行，每行有两个整数 $p_i$ 和 $s_i$，分别表示第 $i$ 个员工的直接上司编号和工资。可以假定编号为 1 的员工为总经理，其上司编号为 0。
接下来的 $q$ 行中，每行描述一个查询，包含两个整数 $c$ 和 $v$。其中，$c$ 指明操作类型，$v$ 为员工编号。如果 $c = 1$，表示进行第一种操作；如果 $c = 2$，表示进行第二种操作。
输入数据保证构成一棵有效的有根树。
输出格式
对于每个测试用例，首先输出一行 "Case X:"，其中 X 表示测试用例编号。然后，针对每个类型为 1 的查询输出工资总和。
说明/提示
- 测试用例数量 $1 \le T \le 10$
- 员工总数 $1 \le N \le 10^5$
- 查询次数 $1 \le q \le 10^5$
- 上司编号 $0 \le p_i \le N$
- 工资 $0 \le s_i \le 10^9$
考虑到数据规模较大，建议使用更高效的输入输出方法。
题目作者：Ahmad Faiyaz
特别感谢：Syed Shahriar Manjur
**本翻译由 AI 自动生成**