#P18751. [KOI2026 一轮] 散步路线

[KOI2026 一轮] 散步路线

[KOI2026 一轮] 散步路线(산책로 / Trail)

题目描述

KOI 山上有 NN 个休息点,编号为 1,2,…,N1,2,\ldots,N,由 N−1N-1 条双向步道连接成一棵树。

休息点 ii 的人群密集度为正整数 AiA_i。第 jj 条步道连接休息点 jj 与 CjC_j,长度为 LjL_j,其中 j+1≤Cj≤Nj+1\le C_j\le N。

你需要选择两个不同的休息点,沿着它们之间唯一的简单路径散步。设路径上所有步道的长度之和为 SS,路径上所有休息点(包括两个端点)的密集度最大值为 MM,则这条路径的满意度定义为

S−M.S-M.

请输出一组使满意度最大的不同休息点编号。最优答案可能为负数。若有多组最优端点,输出任意一组均可。

输入格式

第一行一个整数 NN。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

第三行 N−1N-1 个整数 C1,C2,…,CN−1C_1,C_2,\ldots,C_{N-1}。

第四行 N−1N-1 个整数 L1,L2,…,LN−1L_1,L_2,\ldots,L_{N-1}。

输出格式

输出两个不同的整数 u,vu,v,表示一组最优路径的两个端点。无需输出满意度或路径。

样例 1

2
1 2
2
1
1 2

唯一可选路径的满意度为 1−max⁡(1,2)=−11-\max(1,2)=-1。

样例 2

4
6 10 20 1
2 4 4
3 21 15
1 3

路径 1→2→4→31\to2\to4\to3 的长度为 3+21+15=393+21+15=39,最大密集度为 2020,满意度为 1919,为最大值。六条不同端点路径的满意度依次为:11 到 22 为 −7-7,11 到 33 为 1919,11 到 44 为 1414,22 到 33 为 1616,22 到 44 为 1111,33 到 44 为 −5-5。

数据范围与子任务

所有输入均为整数。

  • 2≤N≤3000002\le N\le300000;
  • 1≤Ai≤10181\le A_i\le10^{18};
  • j+1≤Cj≤Nj+1\le C_j\le N,1≤Lj≤10121\le L_j\le10^{12}。
子任务 分值 附加限制
1 8 N≤300N\le300
2 12 N≤7500N\le7500
3 11 所有 AiA_i 相等
4 15 所有 Cj=j+1C_j=j+1,即链
5 17 所有 Cj=NC_j=N,即以 NN 为中心的星形树
6 36 不同的 AiA_i 至多有 2020 种
7 51 无附加限制

原题满分为 150 分;本资料包保留原子任务及分值。时限 2 秒,内存限制 1024 MiB。