P17138 [KOI 2026 #1] Trail.

There are $N$ rest stops on KOI Mountain, numbered from $1$ to $N$, and $N-1$ undirected trails connecting these rest stops. For each integer $i$ ($1 \le i \le N$), the crowding level of rest stop $i$ is given by a positive integer $A_i$. For each integer $j$ ($1 \le j \le N-1$), trail $j$ connects rest stop $j$ and rest stop $C_j$ ($j+1 \le C_j \le N$), and its length is $L_j$. In other words, all rest stops are connected by these trails to form a tree. The lonely hiker Gyojun wants to choose two different rest stops and walk along the unique simple path between them. For a chosen path, define: - $S$ as the sum of the lengths of all trails on the path. - $M$ as the maximum crowding level among all rest stops on the path. Gyojun wants to walk as far as possible and also enjoy a quiet walk where there are fewer people, so he defines the satisfaction of this path as $S-M$. Write a program to determine which two rest stops Gyojun should choose to maximize the satisfaction of the walking path.

The first line contains an integer $N$. The second line contains $N$ integers $A_1,A_2,\ldots,A_N$, separated by spaces. The third line contains $N-1$ integers $C_1,C_2,\ldots,C_{N-1}$, separated by spaces. The fourth line contains $N-1$ integers $L_1,L_2,\ldots,L_{N-1}$, separated by spaces.

Output two different rest stop indices on the first line, separated by a space, such that the satisfaction of the path between them is maximized. If there are multiple valid answers, output any one of them.

### Sample Explanation 1 The satisfaction of the path between rest stop $1$ and rest stop $2$ is $-1$, and this value is the maximum among all path satisfactions. ### Sample Explanation 2 The satisfactions of all possible paths are as follows: - The satisfaction of path $1-2$ is $3-\max\{6,10\}=3-10=-7$. - The satisfaction of path $1-2-4-3$ is $(3+21+15)-\max\{6,10,20,1\}=39-20=19$. - The satisfaction of path $1-2-4$ is $(3+21)-\max\{6,10,1\}=24-10=14$. - The satisfaction of path $2-4-3$ is $(21+15)-\max\{10,20,1\}=36-20=16$. - The satisfaction of path $2-4$ is $21-\max\{10,1\}=21-10=11$. - The satisfaction of path $3-4$ is $15-\max\{20,1\}=15-20=-5$. ### Constraints - All numbers in the input are integers. - $2 \le N \le 300\,000$. - For each integer $i$ ($1 \le i \le N$), $1 \le A_i \le 10^{18}$. - For each integer $j$ ($1 \le j \le N-1$), $j+1 \le C_j \le N$ and $1 \le L_j \le 10^{12}$. ### Subtasks 1. ($8$ points) $N \le 300$. 2. ($12$ points) $N \le 7\,500$. 3. ($11$ points) $A_1=A_2=\cdots=A_N$. 4. ($15$ points) For each integer $j$ ($1 \le j \le N-1$), $C_j=j+1$. 5. ($17$ points) $C_1=C_2=\cdots=C_{N-1}=N$. 6. ($36$ points) The number of distinct integers in the set $\{A_1,A_2,\ldots,A_N\}$ is at most $20$. 7. ($51$ points) No additional constraints. Translated by ChatGPT-5.6. Translated by ChatGPT 5