Maximizing the Total Difficulty in Independent Set Problems

E.Space loves the maximum weighted independent set problem. Now he has invented a new twist on the problem involving message‐passing among AIs. There are (n) AIs numbered from (1) to (n). Initially, the (i)th AI stores a maximum weighted independent set problem with difficulty (d_i). For every (i) from (2) to (n), the (i)th AI can communicate with the (c_i)th AI (and vice versa); no other pairs of AIs can communicate.\n\nE.Space performs the following operation repeatedly: he selects an AI that currently holds a problem, outputs (publishes) its stored problem, and then clears the problem from that AI. However, just before clearing the problem, the AI sends the problem to every AI with which it can communicate. If a receiving AI already holds a problem with difficulty (x) and it receives a problem of difficulty (y), it combines them into a new problem with difficulty (x+y). (If an AI that does not have a stored problem receives one, it simply discards it.)\n\nThus, by carefully choosing the order in which problems are output, difficulties from one AI can be added into the problems of others. More formally, if we view the process as a removal of nodes from a tree (where an edge exists between (i) and (c_i) for (2 \le i \le n)), when an AI is chosen, its current difficulty is output and then its value is added to each of its adjacent AIs (provided they have not yet published their problem). Note that if a node receives a value, that value may later be transmitted further.\n\nE.Space wishes to maximize the sum of the difficulties of the (n) problems that are eventually output. Equivalently, if the final removal order is (P_1,P_2,\dots,P_n) and if an AI (v) that originally had difficulty (d_v) is removed at position (k) so that it has received contributions from all adjacent AIs removed before it, then its output equals \n[ d_v + \sum_{u:, \text{adjacent to }v \text{ and removed before } v} d_u' ] (in which the contributions are cumulative). It can be shown that there is an optimal removal order which is equivalent to choosing a root (r) and ensuring that for every edge ((u,v)) the AI with the larger difficulty among (u) and (v) is removed earlier. In this way, each edge ((u,v)) effectively contributes (\max(d_u,d_v)) (possibly through transitive additions) to the final total.\n\nYour task is to help E.Space by computing the maximum total difficulty that can be achieved. More precisely, let (total = \sum_{i=1}^n d_i). It turns out that the maximum total difficulty achievable is [ total + \max_{r \in {1,2,\dots,n}} \sum_{v \neq r} d_v \cdot \mathrm{dist}(v,r), ] where (\mathrm{dist}(v,r)) is the distance between nodes (v) and (r) in the tree defined by the communication links.\n\nBelow is the input/output format.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10^5\)), the number of AIs.

The second line contains \(n\) space‐separated integers: \(d_1,d_2,\dots,d_n\), where \(d_i\) is the difficulty of the problem initially stored in the \(i\)th AI.

The third line contains \(n-1\) space‐separated integers: \(c_2,c_3,\dots,c_n\). For every \(i\) with \(2 \le i \le n\), there is a bidirectional communication link between AI \(i\) and AI \(c_i\).

outputFormat

Output a single integer, the maximum total difficulty achievable by optimally choosing the order to output (publish) problems.

sample

2
3 5
1

13