#P18934. [2026多校联测]救援
[2026多校联测]救援
救援
题目描述
A 国形如一棵有根树,其中 号城市是 A 国的首都,其它每个城市都有其上属城市。具体的,第 个城市到其上属城市为 有一条道路,这条道路的长度为 。
我们称一个城市 是城市 的间接附属,当且仅当城市 的上属城市 是城市 ,或者城市 是城市 的间接附属。定义 表示从城市 到城市 的最短路径长度。
由于 A 国天灾频发,各城市消防安全部队需要联合救援。定义城市 消防安全部队的工作量为 ,当城市 消防安全部队前往城市 执行一次任务时,工作量会增加 ,即 。每个城市的初始工作量是 。
中央指挥部总共发出了 条指令:
- :执行任务:城市 发生了一场灾难,命令城市 及其所有间接附属的城市的消防安全部队前往城市 前线支援,执行一次到城市 的任务;
- :查询工作量:查询城市 及其所有间接附属的城市的消防安全部队工作量的总和。
输入格式
第一行给定两个整数 ,分别表示城市数量和指令数量。
接下来 行,第 行给定两个整数 ,分别表示城市 的上属城市以及路径长度。
接下来 行,每行形如:
- :表示第一类指令:执行任务。
- :表示第二类指令:查询工作量。
输出格式
对于每条第二类指令,输出一行一个整数,表示总工作量。
样例 1 输入
5 4
1 3
1 2
2 1
2 2
1 5 1
2 1
1 2 3
2 2
样例 1 输出
5
23
样例 2
见选手目录下的 rescue2.in 与 rescue2.ans。
样例 3
见选手目录下的 rescue3.in 与 rescue3.ans。
样例 4
见选手目录下的 rescue4.in 与 rescue4.ans。
样例 5
见选手目录下的 rescue5.in 与 rescue5.ans。
数据范围
对于所有测试数据,保证:
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| A | ||
| ^ | B | |
| C | ||
| 无 |
- 特殊性质 A:对于所有 ,。
- 特殊性质 B:对于所有 ,。
- 特殊性质 C:对于所有第一类指令,保证 。