#P18751. [KOI2026 一轮] 散步路线
[KOI2026 一轮] 散步路线
[KOI2026 一轮] 散步路线(산책로 / Trail)
题目描述
KOI 山上有 个休息点,编号为 ,由 条双向步道连接成一棵树。
休息点 的人群密集度为正整数 。第 条步道连接休息点 与 ,长度为 ,其中 。
你需要选择两个不同的休息点,沿着它们之间唯一的简单路径散步。设路径上所有步道的长度之和为 ,路径上所有休息点(包括两个端点)的密集度最大值为 ,则这条路径的满意度定义为
请输出一组使满意度最大的不同休息点编号。最优答案可能为负数。若有多组最优端点,输出任意一组均可。
输入格式
第一行一个整数 。
第二行 个整数 。
第三行 个整数 。
第四行 个整数 。
输出格式
输出两个不同的整数 ,表示一组最优路径的两个端点。无需输出满意度或路径。
样例 1
2
1 2
2
1
1 2
唯一可选路径的满意度为 。
样例 2
4
6 10 20 1
2 4 4
3 21 15
1 3
路径 的长度为 ,最大密集度为 ,满意度为 ,为最大值。六条不同端点路径的满意度依次为: 到 为 , 到 为 , 到 为 , 到 为 , 到 为 , 到 为 。
数据范围与子任务
所有输入均为整数。
- ;
- ;
- ,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 8 | |
| 2 | 12 | |
| 3 | 11 | 所有 相等 |
| 4 | 15 | 所有 ,即链 |
| 5 | 17 | 所有 ,即以 为中心的星形树 |
| 6 | 36 | 不同的 至多有 种 |
| 7 | 51 | 无附加限制 |
原题满分为 150 分;本资料包保留原子任务及分值。时限 2 秒,内存限制 1024 MiB。