Problem Description

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.

Input Format

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 Format

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.

2
1 2
2
1

1 2

4
6 10 20 1
2 4 4
3 21 15

1 3

Hint

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