Overview

In a tree-structured communication network, Aoki cuts at most \(1\) edge, and then Takahashi chooses an intrusion point to maximize his profit.
We need to efficiently find the “maximum value Takahashi can obtain” for each possible edge cut, and output the minimum among these values.

Analysis

When Aoki cuts one edge, the tree is divided into \(2\) connected components.
Takahashi chooses a vertex in one of the connected components after the cut as his intrusion point, and steals data from vertices reachable within a distance of \(D\) or less from that vertex.

Naively, we would:

• Try all possible edges for Aoki to cut: \(O(N)\)
• Try all possible intrusion points for Takahashi: \(O(N)\)
• Search for vertices within distance \(D\) each time: \(O(N)\)

This would take \(O(N^3)\) time in total.
Since \(N \leq 3000\), this will result in TLE (Time Limit Exceeded).

Therefore, we reverse our perspective.

Instead of “finding Takahashi’s optimal value for each cut edge”,
we consider “updating the results for all cut edges collectively for each intrusion point \(x\)”.

---

We root the tree at an arbitrary vertex, say vertex \(0\).
Once the tree is rooted, each non-root vertex \(c\) corresponds to the edge \((parent[c], c)\) connecting it to its parent.

Cutting this edge splits the tree into the following \(2\) parts:

• The subtree rooted at vertex \(c\).
• The rest of the tree.

Now, let the intrusion point be \(x\).

First, let \(B_x\) be the total data of vertices within distance \(D\) from \(x\) when no edge is cut.

Also, let \(S_x(c)\) be the total data of vertices that are in the subtree of \(c\) and within distance \(D\) from \(x\).

If we cut the edge \((parent[c], c)\), then:

• If \(x\) is in the subtree of \(c\), the stolen data is \(S_x(c)\).
• If \(x\) is outside the subtree of \(c\), the stolen data is \(B_x - S_x(c)\).

This is because we cannot cross the cut edge.
The distance between any two vertices in the same connected component remains the same as in the original tree.

Therefore, for each edge represented by \(c\),

\[ \max\left( \max_{x \in subtree(c)} S_x(c), \max_{x \notin subtree(c)} (B_x - S_x(c)) \right) \]

is the maximum value Takahashi can steal when that edge is cut.

Since Aoki wants to minimize this value, we take the minimum of this value over all edges.
Also, Aoki can choose “not to cut any edge”, so we must also include the value for this case:

\[ \max_x B_x \]

in our candidates.

Algorithm

1. Root the tree at vertex \(0\).
2. Run a DFS to compute the following:
   • parent[v]: Parent of vertex \(v\)
   • children[v]: Children of vertex \(v\)
   • tin[v], tout[v]: Entry and exit times from an Euler Tour, used to determine subtree membership.
   • order: DFS order (the order in which vertices are visited)

Using the Euler Tour, we can check if vertex \(x\) is in the subtree of \(c\) by:

$\( tin[c] \leq tin[x] < tout[c] \)$

1. For each intrusion point \(x\), perform the following:

   1. Find all vertices within distance \(D\) from \(x\) using DFS/BFS.
   2. For each vertex \(u\), set its value to \(V_u\) if its distance is \(\leq D\), and \(0\) otherwise.
   3. Compute the subtree sums bottom-up on the rooted tree.

   sub[c] will be:

   $\( S_x(c) \)$

   which is “the total data of vertices in the subtree of \(c\) that are within distance \(D\) from \(x\)”.

   1. sub[0] is the total data \(B_x\) that can be stolen from \(x\) if no edge is cut.
      Update noCut using this value.

   2. Update the values for each candidate cut edge, i.e., for each non-root vertex \(c\):

      • If \(x\) is in the subtree of \(c\):

      inMax[c] = max(inMax[c], sub[c]);
      

      • If \(x\) is outside the subtree of \(c\):

      outMax[c] = max(outMax[c], B_x - sub[c]);
      

2. Finally, for each edge \(c\), compute:

$\( \max(inMax[c], outMax[c]) \)$

This represents the maximum data Takahashi can steal if he chooses his intrusion point optimally when that edge is cut.

1. Output the minimum of noCut (the “no-cut” case) and the values obtained for cutting each edge.

Complexity

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

For each intrusion point \(x\), we perform the distance calculation, subtree sum calculation, and edge updates in \(O(N)\) time.
Since there are \(N\) possible intrusion points, the overall complexity is \(O(N^2)\).

Key Implementation Points

• Each edge is represented by the “child vertex \(c\)” in the rooted tree.

  • This corresponds to cutting the edge \((parent[c], c)\).

• We use tin and tout from the Euler Tour to determine subtree membership.

• sub[c] is the total stealable data in the subtree for a fixed intrusion point \(x\).

• Since each value \(V_i\) can be up to \(10^9\), the total sum can be up to around \(3 \times 10^{12}\). Therefore, we must use long long.

• In the distance search, we avoid redundant exploration by stopping once the distance reaches \(D\).

  Source Code

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

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

    int N, D;
    cin >> N >> D;

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

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

    vector<int> tin(N), tout(N), parent(N), order;
    vector<vector<int>> children(N);
    int timer = 0;

    auto dfs = [&](auto self, int u, int p) -> void {
        parent[u] = p;
        tin[u] = timer++;
        order.push_back(u);

        for (int v : g[u]) {
            if (v == p) continue;
            children[u].push_back(v);
            self(self, v, u);
        }

        tout[u] = timer;
    };

    dfs(dfs, 0, -1);

    vector<long long> inMax(N, 0), outMax(N, 0), sub(N, 0);
    vector<int> dist(N);

    long long noCut = 0;

    for (int x = 0; x < N; x++) {
        fill(dist.begin(), dist.end(), D + 1);

        vector<pair<int, int>> st;
        st.reserve(N);
        st.push_back({x, -1});
        dist[x] = 0;

        while (!st.empty()) {
            auto [u, p] = st.back();
            st.pop_back();

            if (dist[u] == D) continue;

            for (int v : g[u]) {
                if (v == p) continue;
                dist[v] = dist[u] + 1;
                st.push_back({v, u});
            }
        }

        for (int i = N - 1; i >= 0; i--) {
            int u = order[i];
            long long s = (dist[u] <= D ? V[u] : 0LL);
            for (int v : children[u]) {
                s += sub[v];
            }
            sub[u] = s;
        }

        long long ball = sub[0];
        noCut = max(noCut, ball);

        int tx = tin[x];

        for (int c = 1; c < N; c++) {
            if (tin[c] <= tx && tx < tout[c]) {
                inMax[c] = max(inMax[c], sub[c]);
            } else {
                outMax[c] = max(outMax[c], ball - sub[c]);
            }
        }
    }

    long long ans = noCut;

    for (int c = 1; c < N; c++) {
        ans = min(ans, max(inMax[c], outMax[c]));
    }

    cout << ans << '\n';

    return 0;
}

---

This editorial was generated by gpt-5.5-high.