题目描述

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}$，整数之间以空格分隔。

输出格式

第一行输出两个不同的休息站编号，编号之间以空格分隔，使得这两个休息站之间路径的满意度最大。

如果存在多种可行的输出，输出其中任意一种均可。

2
1 2
2
1

1 2

4
6 10 20 1
2 4 4
3 21 15

1 3

提示

样例说明 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 完成