Overview

In the occupation game, no matter how the players play, all cities in the target tree will eventually be occupied.
Therefore, it is optimal for Aoki to remove the “subtree with the maximum total value” in Phase 1.

Analysis

Cities Eventually Occupied in the Occupation Game

In Phase 2, a player must occupy exactly one occupiable city on their turn, and passing is not allowed.

The target graph is a rooted tree, and the root, City \(1\), is occupiable from the beginning.

The crucial point here is that as long as there are unoccupied cities remaining in the target tree, there is always at least one occupiable city.

This is because if we choose any unoccupied city \(x\) and consider the path from the root to \(x\), there must be an unoccupied city on this path that immediately follows an already occupied city.
Since its parent is occupied, this city is occupiable.

Therefore, the game ends when all cities in the target tree are occupied.

In other words, the players’ choices in Phase 2 do not affect the final total value.

---

What Aoki Can Do in Phase 1

Aoki can either block one edge or do nothing.

If he blocks the edge \((P_i, i)\), the component that does not contain City \(1\) becomes the subtree rooted at City \(i\).

Therefore, the final total value obtained in that case is:

\(\text{Total Sum} - \text{Subtree Sum of City } i\)

Since Aoki wants to minimize this value, he wants to remove a subtree with the maximum possible sum.

However, if the subtree sum is negative, removing it would instead increase the total value.
Therefore, if the sums of all subtrees are less than or equal to \(0\), it is optimal for Aoki to not block any edge.

Thus, the answer is:

\(\text{Total Sum} - \max(0, \text{maximum subtree sum among all cities except the root})\)

---

Why the Naive Approach is Difficult

If we model Phase 2 as a standard game and perform minimax by listing all possible cities to choose at each turn, the number of choices becomes extremely large, leading to exponential time complexity.

Additionally, if we calculate the subtree sum using DFS or a similar method every time we block an edge, it will take \(O(N^2)\) time in the worst case.
Since \(N \leq 5 \times 10^5\), this will not run within the time limit.

Instead, we can compute the sum of the subtree rooted at each city in a single backward pass.

Algorithm

1. Prepare an array sub to store the subtree sum for each city, initialized with sub[i] = V_i.
2. Iterate through the city indices in reverse order, from \(N\) down to \(2\).
   • By the constraints, \(P_i < i\), which means the parent always has a smaller index than its children.
   • Therefore, by processing in reverse order, all descendants of City \(i\) will have already been added to sub[i].
3. For each city \(i\):
   • Consider sub[i] as a candidate for the “removable subtree sum”.
   • Record its maximum value in best.
   • Add sub[i] to its parent P_i.
4. Finally, sub[1] will represent the total sum of the entire tree.
5. The answer is sub[1] - best.
   • By initializing best to \(0\), we can naturally handle the case where “no edge is blocked”.

For example, if a certain subtree has a sum of \(10\), removing it reduces the final total by \(10\).
On the other hand, if the maximum subtree sum is negative, there is no benefit in removing it, so best remains \(0\), and the total sum becomes the answer.

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Points

Since the condition \(P_i < i\) holds, there is no need to construct an adjacency list and perform a DFS.
By processing the city indices in descending order, we can find the subtree sums simply by adding each city’s subtree sum to its parent.

Also, since the value of \(V_i\) can be up to \(10^9\) and the number of cities is up to \(5 \times 10^5\), the total sum may exceed the range of a 32-bit integer.
While you do not need to worry about integer overflow in Python, you must use 64-bit integers in other languages.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = [0] + data[1:1+n]

    if n == 1:
        print(v[1])
        return

    parents = [0] * (n + 1)
    idx = 1 + n
    for i in range(2, n + 1):
        parents[i] = data[idx]
        idx += 1

    sub = v[:]
    best = 0

    for i in range(n, 1, -1):
        s = sub[i]
        if s > best:
            best = s
        sub[parents[i]] += s

    print(sub[1] - best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.