Summary

In the occupation game, all cities in the target game tree will eventually be occupied.
Therefore, the problem reduces to “which subtree Aoki should cut off to minimize Takahashi’s score”.

Analysis

All cities are always occupied in the occupation game

The tree used in the game is a connected rooted tree with city \(1\) as the root.

Initially, city \(1\) is available for occupation.
Once a city is occupied, its children become newly available for occupation.

Suppose there are still unoccupied cities remaining.
If we consider the unoccupied city closest to the root, its parent must have already been occupied.
Therefore, that city is available for occupation.

In other words, as long as there are unoccupied cities, there is always at least one city available for occupation.
Thus, the game ends when all cities in the target tree have been occupied.

Therefore, which cities Takahashi and Aoki choose in Phase 2 does not affect the final set \(S\).
The final score is simply “the sum of the values of the cities remaining in the tree”.

What Aoki can do

In Phase 1, Aoki can choose to:

• Cut exactly one edge
• Or not cut any edge

Cutting the edge connecting city \(i\) (\(i \geq 2\)) and its parent removes the entire subtree rooted at city \(i\) from the game.

Let \(total\) be the sum of the values of all original cities, and \(sub_i\) be the sum of the values of the subtree rooted at city \(i\). The score after cutting that edge is:

\( total - sub_i \)

Since Aoki wants to minimize this value, he should remove the subtree with the maximum possible \(sub_i\).

However, choosing not to cut any edge is also an option.
This can be thought of as “removing a total value of \(0\)”.

Therefore, the maximum value that can be removed is:

\( \max(0, sub_2, sub_3, \ldots, sub_N) \)

The answer is:

\( total - \max(0, sub_2, sub_3, \ldots, sub_N) \)

Why a naive approach fails

If we search Phase 2 of the game naively using minimax, the number of ways to choose the occupation order is extremely large, leading to exponential time complexity.

Also, recalculating the sum of the remaining tree every time we cut an edge would take \(O(N^2)\) in the worst case, which is too slow for \(N \leq 5 \times 10^5\).

Instead, we calculate the sum of the subtree rooted at each city only once.

Algorithm

1. Construct the tree (e.g., using child lists or parent-child relationships).
2. For each city \(i\), calculate the subtree sum \(sub_i\).
3. Find the maximum value of \(sub_i\) for \(i = 2, 3, \ldots, N\).
4. Initialize the maximum value to \(0\) to account for the “do not cut” option.
5. Output \(total - best\_remove\) as the answer.

In this problem, the parent \(P_i\) always satisfies \(P_i < i\).
That is, the parent’s index is always smaller than the child’s index.

Therefore, if we process the city indices in reverse order from \(N\) down to \(1\), the subtree sums of the children will already have been calculated.

For each city \(i\), we can calculate:

\( sub_i = V_i + \sum_{c: \text{child of } i} sub_c \)

Complexity

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

Implementation Details

Since the subtree sums and the total sum can have large absolute values, use 64-bit integers (long long).

Additionally, since \(N\) can be as large as \(5 \times 10^5\), using recursive DFS might cause a stack overflow.
In our implementation, we take advantage of the property \(P_i < i\) and process the city indices in reverse order to calculate the subtree sums without using recursion.

It is also important to initialize best_remove to 0.
If all subtree sums are negative, cutting any edge would increase the score. In this case, it is optimal for Aoki not to cut any edge.

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> V(N + 1);
    for (int i = 1; i <= N; i++) cin >> V[i];

    vector<vector<int>> children(N + 1);
    for (int i = 2; i <= N; i++) {
        int p;
        cin >> p;
        children[p].push_back(i);
    }

    vector<long long> sub(N + 1);
    long long total = 0;

    for (int i = N; i >= 1; i--) {
        sub[i] += V[i];
        total += V[i];
        for (int c : children[i]) {
            sub[i] += sub[c];
        }
    }

    long long best_remove = 0;
    for (int i = 2; i <= N; i++) {
        best_remove = max(best_remove, sub[i]);
    }

    cout << total - best_remove << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.