Overview

This problem asks us to find the value of a minimax (minimization and maximization) game played on a tree network. Aoki tries to minimize Takahashi’s payoff by “cutting at most one edge,” while Takahashi tries to maximize the “sum of data of vertices within distance \(D\) from some vertex.”

Analysis

Game Structure

This game is a sequential minimax game.

• Aoki’s actions consist of “not cutting any edge” or “cutting one of the \(N-1\) edges”, giving a total of \(N\) choices.
• In response to each action, Takahashi chooses a vertex \(v\) to maximize the “sum of data within distance \(D\) from \(v\).”

Therefore, the answer we seek is:

\[ \min_{\text{Aoki's action}} \left( \max_{v} \big(\text{sum of data within distance } D \text{ from } v\big) \right) \]

We need to find the “maximum payoff when no edge is cut” and the “maximum payoff when each edge is cut,” and the minimum among these will be the answer.

Issue with the Naive Approach

A naive calculation of “Aoki’s \(N\) actions \(\times\) Takahashi’s \(N\) vertices \(\times\) \(O(N)\) search within distance \(D\) from each vertex” would result in \(O(N^3)\) time complexity. For \(N \le 3000\), this requires about \(2.7 \times 10^{10}\) operations, which is too slow to pass within the time limit.

Key Idea

The key is to fix the vertex \(v\) chosen by Takahashi and consider the tree rooted at \(v\). This allows us to process “which edge to cut” all at once in a single search.

We perform a BFS rooted at \(v\) to find the depth (distance from \(v\)) of each vertex \(x\). Here, we define:

\[ \text{subval}[x] = \sum_{\substack{y \in (\text{subtree rooted at } x)\\ \text{dist}(v,y)\le D}} V[y] \]

This represents the “sum of data of vertices within distance \(D\) from \(v\) that belong to the subtree rooted at \(x\).” By accumulating the values from the leaves up to the root, we can compute this for all vertices in \(O(N)\) time.

In this case:

• Takahashi’s payoff at \(v\) when no edge is cut is \(f = \text{subval}[v]\) (the sum of data within distance \(D\) in the entire tree).
• Takahashi’s payoff at \(v\) when the edge \(e\) to the parent of \(x\) is cut is

\[ f - \text{subval}[x] \]

since the subtree rooted at \(x\) is disconnected from \(v\) (the amount lost within distance \(D\) is exactly \(\text{subval}[x]\)).

Since edge \(e\) is always a tree edge, rooting the tree at \(v\) always splits it into a “parent-side component” and a “child-side component containing \(x\).” Thus, with a single BFS, we can simultaneously find the payoffs for both “not cutting” and “cutting each edge” when \(v\) is chosen as the center.

Algorithm

For each vertex \(v = 1,2,\ldots,N\), perform the following steps:

1. Run a BFS rooted at \(v\) to find the depth, parent, and the index of the edge to the parent for each vertex.
2. Initialize \(\text{subval}[x]\) for each vertex \(x\) (set to \(V[x]\) if the distance is within \(D\), and \(0\) otherwise), and accumulate these values to their parents in the reverse order of the BFS.
3. Update the maximum value of noCut (the candidate for “not cutting”) with \(f = \text{subval}[v]\).
4. For each vertex \(x\) (except \(v\)), update \(M[e]\) (the maximum payoff when edge \(e\) is cut) with the payoff \(f - \text{subval}[x]\), where \(e\) is the edge to the parent of \(x\).

Finally, output:

\[ \text{Answer} = \min\Big(\text{noCut},\ \min_{e} M[e]\Big) \]

Here, noCut corresponds to Aoki’s choice of “not cutting any edge,” and \(M[e]\) corresponds to the choice of “cutting edge \(e\).” Aoki will choose the action that minimizes this value.

Complexity

• Time Complexity: \(O(N^2)\) (BFS and accumulation centered at each vertex take \(O(N)\) time, performed \(N\) times)
• Space Complexity: \(O(N)\) (for adjacency lists and work arrays)

Since \(N \le 3000\), \(O(N^2) \approx 9 \times 10^6\) operations, which is fast enough to pass.

Implementation Details

• By storing the BFS traversal order order and accumulating the values to the parents in its reverse order, we can compute the subtree sums without using recursion (which also avoids stack overflow).

• Since the maximum value of data is \(10^9\) and the number of vertices is up to \(3000\), the total sum can reach up to \(3 \times 10^{12}\). Therefore, using long long (64-bit integer) is essential.

• Note that “the maximum payoff when edge \(e\) is cut, \(M[e]\)” is the maximum value over all possible centers \(v\). This forms a two-stage optimization where Aoki finally chooses the minimum among these values.

  Source Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int N, D;
    scanf("%d %d",&N,&D);
    vector<long long> V(N+1);
    for(int i=1;i<=N;i++) scanf("%lld",&V[i]);
    vector<vector<pair<int,int>>> adj(N+1);
    for(int i=0;i<N-1;i++){
        int a,b; scanf("%d %d",&a,&b);
        adj[a].push_back({b,i});
        adj[b].push_back({a,i});
    }
    vector<long long> M(max(0,N-1), 0);
    vector<int> depth(N+1), par(N+1), parentEdge(N+1);
    vector<int> order; order.reserve(N);
    vector<long long> subval(N+1);
    long long noCut = 0;
    vector<int> qbuf(N);
    for(int v=1; v<=N; v++){
        order.clear();
        for(int i=1;i<=N;i++) depth[i]=-1;
        depth[v]=0; par[v]=0; parentEdge[v]=-1;
        int head=0, tail=0;
        qbuf[tail++]=v;
        while(head<tail){
            int x=qbuf[head++]; order.push_back(x);
            for(auto &pr: adj[x]){
                int y=pr.first, eid=pr.second;
                if(depth[y]==-1){
                    depth[y]=depth[x]+1; par[y]=x; parentEdge[y]=eid;
                    qbuf[tail++]=y;
                }
            }
        }
        for(int x=1;x<=N;x++) subval[x] = (depth[x]<=D ? V[x] : 0LL);
        for(int i=(int)order.size()-1;i>=1;i--){
            int x=order[i];
            subval[par[x]] += subval[x];
        }
        long long f = subval[v];
        if(f>noCut) noCut=f;
        for(int i=1;i<(int)order.size();i++){
            int x=order[i];
            long long val = f - subval[x];
            int e = parentEdge[x];
            if(val > M[e]) M[e]=val;
        }
    }
    long long ans = noCut;
    for(int i=0;i<N-1;i++) ans = min(ans, M[i]);
    printf("%lld\n", ans);
    return 0;
}

---

This editorial was generated by claude4.8opus-high.