Overview

In a tree-structured city, Aoki first blocks one edge, and then Takahashi and Aoki play a game where they take turns occupying cities. Takahashi aims to maximize the sum of the resource values of the occupied cities, while Aoki aims to minimize it. The problem asks for the final sum of resource values when both players play optimally.

Analysis

First, let’s consider only Phase 2, the “occupation game”. Once the parent of a city is occupied, that city becomes available for occupation. The player whose turn it is chooses one available city and occupies it.

Takahashi wants to maximize the total resource value, so he will actively try to occupy cities where the sum of resource values in the subtree (subtree sum) is positive. On the other hand, Aoki wants to minimize it, so he will try to occupy cities where the subtree sum is negative. If Takahashi occupies a certain city \(v\), for its descendant cities, Takahashi will enter and occupy those with positive subtree sums, and Aoki will enter and occupy those with negative subtree sums. As a result, the score of the subtree Takahashi enters becomes the sum of that entire subtree. Similarly, the score of the subtree Aoki enters also becomes the sum of that entire subtree.

Since it is more beneficial for players to enter subtrees that yield profits for themselves rather than trying to obstruct the opponent, the final score at the end of the game will ultimately be equal to the “sum of the resource values of the entire tree”.

Next, let’s consider Phase 1, the “road blockade”. Aoki wants to minimize the score (the sum of the entire tree). Blocking an edge removes the subtree beyond that edge from the game. If the sum of the blocked subtree is positive, this positive value is subtracted from the overall score, shaving off the profit Takahashi would have gained. Conversely, if the sum of the blocked subtree is negative, the overall score would increase, which is disadvantageous for Aoki.

Therefore, it is optimal for Aoki to cut off the subtree with the largest sum among those with a positive subtree sum. If there is no subtree with a positive sum, the optimal choice is not to block any edge (i.e., not shaving off anything).

Algorithm

1. For each vertex \(i\), calculate the sum of the resource values of the subtree rooted at that vertex, subtree_sum[i]. This can be found in \(O(N)\) time by processing the vertices in reverse order (from leaves to the root).
2. Get the total sum of the resource values of the entire tree, total_sum, as subtree_sum[1].
3. Find the maximum of subtree_sum[i] among all vertices \(i\) (\(2 \leq i \leq N\)), and let this be max_removed. Note that the initial value of max_removed should be set to \(0\), so that \(0\) is chosen if there are no positive subtree sums.
4. The answer is total_sum - max_removed.

Complexity

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

Implementation Points

• If \(N = 1\), the third line of the input does not exist, so handle this as a special case and output \(V_1\) as is.

• Since the array of parents \(P\) given in the input contains information for cities \(2\) to \(N\), pay attention to the indices when processing, as its length is \(N-1\).

  Source Code

import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    V = list(map(int, input().split()))
    if N == 1:
        print(V[0])
        return
    P = list(map(int, input().split()))
    
    subtree_sum = [0] * (N + 1)
    for i in range(1, N + 1):
        subtree_sum[i] = V[i-1]
        
    for i in range(N, 1, -1):
        p = P[i-2]
        subtree_sum[p] += subtree_sum[i]
        
    total_sum = subtree_sum[1]
    max_removed = 0
    for i in range(2, N + 1):
        if subtree_sum[i] > max_removed:
            max_removed = subtree_sum[i]
            
    print(total_sum - max_removed)

if __name__ == '__main__':
    solve()

This editorial was generated by or-glm5.2-high.