Overview

This problem is a minimax game (a game where one player aims to maximize and the other aims to minimize) on a tree-structured network. Aoki, the administrator, can “cut one connection (or do nothing)” to minimize the maximum total amount of data that Takahashi, the attacker, can steal from base stations within distance \(D\) of his intrusion point.

Given the constraint \(N \le 3000\), a naive \(O(N^3)\) simulation of all edge cuts and intrusion points will not pass within the time limit. However, we can solve the problem in \(O(N^2)\) time by shifting our perspective: “Fix Takahashi’s intrusion point \(u\) and consider the impact of cutting each edge.”

---

Analysis

1. Game Rules and Objective

When Aoki cuts an edge \(e\) (or does nothing), the tree is divided into two connected components. Takahashi then chooses an intrusion point \(u\) from one of the components and maximizes the sum of data from the vertices within distance \(D\) of \(u\) in that component.

Aoki chooses an edge \(e\) (or no edge) to minimize the maximum data Takahashi can obtain.

2. Limits of the Naive Approach

If we actually cut each of the \(N-1\) edges \(e\) and run a BFS from every vertex \(u\) in the remaining graph to calculate the obtained data, it would take \(O(N)\) per BFS. This results in an overall time complexity of \(O(N^3)\), which is too slow to pass within the time limit.

3. Shift of Perspective: Fixing the Intrusion Point \(u\)

Instead of fixing the edge to cut, let’s consider fixing Takahashi’s intrusion point \(u\).

Let \(S_u\) be the set of vertices reachable from \(u\) within distance \(D\) when no edges are cut, and let \(W_u\) be the sum of their data amounts.

Now, consider cutting some edge \(e\). In the tree rooted at \(u\), if the edge \(e\) connects vertex \(x\) to its parent \(p\), cutting \(e\) means all vertices belonging to the subtree \(T_x\) rooted at \(x\) become unreachable from \(u\).

Therefore, when edge \(e = (p, x)\) is cut, the amount of data Takahashi can obtain by intruding at \(u\) is: $\(W_u - (\text{sum of data of vertices in subtree } T_x \text{ that are within distance } D \text{ from } u)\)$

Cutting any edge not on the path from \(u\) to \(S_u\) (i.e., not leading to a subtree \(T_x\) from \(u\)’s perspective) does not affect the reachability from \(u\) to \(S_u\). Thus, the obtained data amount remains \(W_u\).

Using this property, with just a single search (BFS) starting from \(u\), we can efficiently compute the data amounts obtained on \(u\)’s side for all possible edge cuts \(e\).

---

Algorithm

For each edge \(i\) (connecting \(A_i\) and \(B_i\)), we maintain the following information: - max_val[i][0]: Takahashi’s maximum obtained data in the component containing \(A_i\) when edge \(i\) is cut - max_val[i][1]: Takahashi’s maximum obtained data in the component containing \(B_i\) when edge \(i\) is cut

For each vertex \(u \in \{1, 2, \dots, N\}\), we perform the following steps:

1. Shortest Path Calculation (BFS) Run a BFS starting from \(u\) to find the distance dist to all other vertices. At the same time, record the BFS traversal order (topological order) and the “parent” of each vertex.

2. Initialization of Weights For each vertex \(i\) whose distance from \(u\) is at most \(D\), set sum_val[i] = V[i]; for other vertices, set it to 0. Calculate the total sum \(W_u\) of these values.

3. Bottom-Up Subtree Sum Calculation Accumulate sum_val from children to parents in the reverse of the BFS traversal order (from leaves to the root). $\( \text{sum\_val}[\text{parent}] \leftarrow \text{sum\_val}[\text{parent}] + \text{sum\_val}[\text{child}] \)\( As a result, for each vertex \)x\(, `sum_val[x]` will represent the "sum of data of vertices in the subtree of \)x\( that are within distance \)D\( from \)u$“.

4. Update Values for the Component Containing \(u\) When Each Edge Is Cut For each vertex \(x\) (\(x \neq u\)), consider cutting the edge \(e\) (with index \(idx\)) connecting \(x\) to its parent \(p\). Since \(u\) belongs to the side of \(p\), we update the value of max_val[idx][side] corresponding to the side containing \(p\) with \(W_u - \text{sum\_val}[x]\) using a maximum operation (i.e., max_val[idx][side] = max(max_val[idx][side], W_u - sum_val[x])).

After repeating the above steps for all \(u\), we determine Aoki’s optimal strategy (minimizing the maximum obtained data). - The maximum obtained data when no edge is cut: \(M_0 = \max_u W_u\) - The maximum obtained data when edge \(i\) is cut: \(\max(\text{max\_val}[i][0], \text{max\_val}[i][1])\)

The minimum value among all these choices (\(N\) options in total) is the answer.

---

Complexity

Time Complexity: \(O(N^2)\)

• For each vertex \(u\) (\(N\) options):
  • Distance and parent calculations using BFS: \(O(N)\)
  • Bottom-up subtree sum calculations from leaves to the root: \(O(N)\)
  • Updating max_val for each edge: \(O(N)\)
• Thus, the overall time complexity is \(O(N^2)\). For \(N \le 3000\), the loop runs at most around \(9 \times 10^6\) times, which easily runs well within the time limit (typically 2.0 seconds), taking only a few tens of milliseconds.

Space Complexity: \(O(N)\)

• The adjacency list of the graph, the arrays storing distances and parents, and the max_val array are all of size \(O(N)\). Thus, the space complexity is \(O(N)\), which is extremely lightweight and easily fits within the memory limit.

---

Implementation Details

• Reusing the BFS traversal order: Typically, bottom-up subtree computations use the post-order traversal of a DFS (Depth-First Search). However, by processing the BFS queue order in reverse (from back to front), we can obtain the reverse topological order in \(O(N)\) without performing an additional DFS.

• Determining the direction of edges: When edge \(i\) is cut, we need to determine whether the parent \(p\) is \(A_i\) or \(B_i\), and update the appropriate side of max_val[idx][0] or max_val[idx][1]. In the implementation, this can be determined cleanly using side = (p == A[idx] ? 0 : 1).

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>

using namespace std;

struct Edge {
    int to;
    int idx;
};

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, D;
    if (!(cin >> N >> D)) return 0;

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

    vector<int> A(N - 1), B(N - 1);
    vector<vector<Edge>> adj(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        cin >> A[i] >> B[i];
        adj[A[i]].push_back({B[i], i});
        adj[B[i]].push_back({A[i], i});
    }

    // max_val[i][0] : 辺 i を切ったときの A[i] 側のコンポーネントにおける最大データ量
    // max_val[i][1] : 辺 i を切ったときの B[i] 側のコンポーネントにおける最大データ量
    vector<array<long long, 2>> max_val(N - 1, {0, 0});

    vector<int> dist(N + 1);
    vector<int> parent(N + 1);
    vector<int> edge_to_parent(N + 1);
    vector<int> q;
    q.reserve(N);
    vector<long long> sum_val(N + 1);

    long long M0 = 0;

    for (int u = 1; u <= N; ++u) {
        fill(dist.begin(), dist.end(), -1);
        q.clear();

        // BFSで各頂点への距離を求める
        dist[u] = 0;
        q.push_back(u);
        int head = 0;
        while (head < (int)q.size()) {
            int curr = q[head++];
            for (auto& edge : adj[curr]) {
                int next = edge.to;
                int idx = edge.idx;
                if (dist[next] == -1) {
                    dist[next] = dist[curr] + 1;
                    parent[next] = curr;
                    edge_to_parent[next] = idx;
                    q.push_back(next);
                }
            }
        }

        // 距離 D 以下の頂点の重みの総和 Wu を求める
        long long Wu = 0;
        for (int i = 1; i <= N; ++i) {
            if (dist[i] <= D) {
                Wu += V[i];
                sum_val[i] = V[i];
            } else {
                sum_val[i] = 0;
            }
        }
        M0 = max(M0, Wu);

        // ボトムアップに部分木内の D 以下の重み総和を累積
        for (int i = N - 1; i >= 1; --i) {
            int x = q[i];
            int p = parent[x];
            sum_val[p] += sum_val[x];
        }

        // 各辺を切ったときの u 側コンポーネントの値を更新
        for (int i = N - 1; i >= 1; --i) {
            int x = q[i];
            int p = parent[x];
            int idx = edge_to_parent[x];
            int side = (p == A[idx] ? 0 : 1);
            max_val[idx][side] = max(max_val[idx][side], Wu - sum_val[x]);
        }
    }

    // 青木君は高橋君の獲得量を最小化する
    long long ans = M0;
    for (int i = 0; i < N - 1; ++i) {
        long long current_max = max(max_val[i][0], max_val[i][1]);
        ans = min(ans, current_max);
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-high.