P17138 [KOI 2026 #1] 步道

KOI 山上共有 $N$ 个休息站，编号为 $1$ 到 $N$，以及连接这些休息站的 $N-1$ 条双向步道。 对于每个整数 $i$（$1 \le i \le N$），休息站 $i$ 的拥挤程度用正整数 $A_i$ 表示。 对于每个整数 $j$（$1 \le j \le N-1$），第 $j$ 条步道连接休息站 $j$ 与休息站 $C_j$（$j+1 \le C_j \le N$），其长度为 $L_j$。也就是说，所有休息站通过这些步道连接成一棵树。 孤独的徒步者教俊打算选择两个不同的休息站，并沿着这两个休息站之间唯一的简单路径散步。 对于选定的一条路径，定义： - $S$ 为该路径所包含的所有步道的长度之和； - $M$ 为该路径所包含的所有休息站的拥挤程度的最大值。 教俊既希望尽可能延长散步距离，又希望在人少的地方独自享受散步，因此将这条路径的满意度定义为 $S-M$。 请编写一个程序，求出教俊应当选择哪两个休息站，才能使散步路径的满意度最大。

第一行输入一个整数 $N$。 第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，整数之间以空格分隔。 第三行输入 $N-1$ 个整数 $C_1,C_2,\ldots,C_{N-1}$，整数之间以空格分隔。 第四行输入 $N-1$ 个整数 $L_1,L_2,\ldots,L_{N-1}$，整数之间以空格分隔。

第一行输出两个不同的休息站编号，编号之间以空格分隔，使得这两个休息站之间路径的满意度最大。 如果存在多种可行的输出，输出其中任意一种均可。

### 样例说明 1 休息站 $1$ 与休息站 $2$ 之间路径的满意度为 $-1$，且该值为所有路径满意度中的最大值。 ### 样例说明 2 所有可能路径的满意度如下： - 路径 $1-2$ 的满意度为 $3-\max\{6,10\}=3-10=-7$。 - 路径 $1-2-4-3$ 的满意度为 $(3+21+15)-\max\{6,10,20,1\}=39-20=19$。 - 路径 $1-2-4$ 的满意度为 $(3+21)-\max\{6,10,1\}=24-10=14$。 - 路径 $2-4-3$ 的满意度为 $(21+15)-\max\{10,20,1\}=36-20=16$。 - 路径 $2-4$ 的满意度为 $21-\max\{10,1\}=21-10=11$。 - 路径 $3-4$ 的满意度为 $15-\max\{20,1\}=15-20=-5$。 ### 限制条件 - 输入中给出的所有数均为整数。 - $2 \le N \le 300\,000$。 - 对于每个整数 $i$（$1 \le i \le N$），均有 $1 \le A_i \le 10^{18}$。 - 对于每个整数 $j$（$1 \le j \le N-1$），均有 $j+1 \le C_j \le N$ 且 $1 \le L_j \le 10^{12}$。 ### 子任务 1. （$8$ 分）$N \le 300$。 2. （$12$ 分）$N \le 7\,500$。 3. （$11$ 分）$A_1=A_2=\cdots=A_N$。 4. （$15$ 分）对于每个整数 $j$（$1 \le j \le N-1$），均有 $C_j=j+1$。 5. （$17$ 分）$C_1=C_2=\cdots=C_{N-1}=N$。 6. （$36$ 分）集合 $\{A_1,A_2,\ldots,A_N\}$ 中不同整数的数量不超过 $20$。 7. （$51$ 分）无附加限制。 翻译由 ChatGPT-5.6 完成