#P17801. [Ontak2024]PRO
[Ontak2024]PRO
题目描述
有一棵 个顶点的无权树,顶点编号为 到 。第 个顶点初始有 个机器人,其工厂初始每天生产 个机器人。
观察接下来的 天。每天早晨,各工厂按当前日产量生产机器人。某些天的晚上会发生一个事件,同一天至多一个:
- 修改:将顶点 的工厂日产量改为 ,此修改从下一天早晨的生产开始生效。
- 查询:选择一个顶点作为会场,把所有机器人临时运到那里。设当前顶点 有 个机器人,将会场选在 的费用为
其中 为树上路径的边数。查询结束后机器人立即回到原处,因此查询不会改变后续的机器人数量。
对每次查询,输出最小费用及取得该费用的最小顶点编号。
输入格式
第一行整数 ,为子任务编号。
第二行三个整数 ,为顶点数、事件数、观察天数。
第三行 个整数 ,第四行 个整数 。
接下来 行,每行两个整数 ,描述树的一条边。
最后 行按时间顺序描述事件:
1 ti vi ci
表示第 天晚上把工厂 的日产量改为 ;
2 ti
表示第 天晚上查询会场。
输出格式
对每个类型 的事件,输出一行两个整数 费用 顶点编号。
数据范围
- ,。
- 。
- ,输入边构成树;修改的顶点也是树中顶点。
- 。
- 至少有一个类型 的事件。
原题信息缺项: 当前官方 PDF 没有单独列出修改值 的数值范围。本稿保留这一缺项,不擅自补成 ;若用于重新出题或制作数据,需要向原题包/出题方进一步核实。
原题提示:C++ 编译器支持有符号 __int128,该类型的常规流输入输出需要自行处理。本题要求输出精确整数,不取模。
样例 1
输入:
0
4 5 10
1 3 2 8
3 2 5 1
1 2
1 3
1 4
2 1
2 5
1 6 2 25
2 7
2 10
输出:
21 1
72 4
121 1
225 2
样例 2
输入:
0
4 2 100
3 3 3 3
7 7 7 7
1 2
2 3
3 4
2 31
2 100
输出:
400 2
1228 2
子任务
| 编号 | 附加限制 | 分值 |
|---|---|---|
| 1 | 11 | |
| 2 | ||
| 3 | 5 | |
| 4 | 类型 的事件至多 10 个 | 26 |
| 5 | 类型 的事件至多 10 个 | 12 |
| 6 | 无附加限制 | 35 |