#GYM104598D. Intergalactic Terrorism
Intergalactic Terrorism
Description
Kafka wants to cause some trouble at the Xianzhou Luofu. She is currently at the Ambrosial Arbor, which is a large tree with $n$ ($2 \le n \le 10^5$). In the tree, node $i$ has an explosion value of $a_i$ ($1 \le a_i \le 10^8$), and the edges all have weight $1$. If a simple cycle is created in the tree, it will explode with a magnitude of the sum of edge weights on the cycle. In order to carry out her terrorism, Kafka will add an edge between two nodes $u$ and $v$ with weight $a_u + a_v$, thus creating a simple cycle and exploding the tree. Note that $u \ne v$.
As a wanted terrorist, Kafka wants to cause as large an explosion as possible, so please tell her the largest magnitude explosion that she could cause by adding any edge.
The first line contains a single integer $n$ ($2 \le n \le 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^8$).
The third line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), meaning that there is an edge between node $p_i$ and node $i$, and node $p_i$ is a parent of node $i$.
The output should consist of a single integer denoting the largest magnitude of an explosion that Kafka can create.
Input
The first line contains a single integer $n$ ($2 \le n \le 10^5$).
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^8$).
The third line contains $n - 1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), meaning that there is an edge between node $p_i$ and node $i$, and node $p_i$ is a parent of node $i$.
Output
The output should consist of a single integer denoting the largest magnitude of an explosion that Kafka can create.
5
1 2 3 3 3
1 1 2 4
5
10 1 1 1 1
1 1 3 4
10
14