概要

この問題は、木構造のネットワークにおいて、管理者の青木君が「回線を1本遮断する（またはしない）」ことで、攻撃者の高橋君が「侵入先から距離 \(D\) 以内の基地局から盗み出せるデータの最大合計量」を最小化する、ミニマックスゲーム（一方が最大化、他方が最小化を目指すゲーム）です。

制約 \(N \le 3000\) から、すべての辺の組み合わせを愚直にシミュレーションする \(O(N^3)\) の方法では間に合いませんが、「高橋君の侵入先 \(u\) を固定して、辺を切ったときの影響を考える」 という視点の転換を行うことで、\(O(N^2)\) で解くことができます。

---

考察

1. ゲームのルールと目的

青木君が辺 \(e\) を遮断した（または何も遮断しなかった）とき、木は2つの連結成分（コンポーネント）に分かれます。 高橋君はどちらかのコンポーネントから侵入先 \(u\) を選び、そのコンポーネント内で \(u\) から距離 \(D\) 以内にある頂点のデータ量の総和を最大化します。

青木君は、高橋君が獲得できる最大値を最も小さくするような辺 \(e\) を選択します。

2. ナイーブな手法の限界

すべての辺 \(e\) （\(N-1\) 通り）について実際に切断し、残されたグラフで全頂点 \(u\) からBFS等を行って獲得量を求めると、1回のBFSに \(O(N)\) かかるため、全体で \(O(N^3)\) となり実行時間制限に間に合いません。

3. 視点の転換：侵入先 \(u\) を固定する

辺を固定するのではなく、高橋君の侵入先 \(u\) を固定して考えてみましょう。

頂点 \(u\) から出発して、何も辺を切らない場合に距離 \(D\) 以下で到達できる頂点の集合を \(S_u\) とし、そのデータ量の総和を \(W_u\) とします。

ここで、ある辺 \(e\) を切ることを考えます。 \(u\) を根とする木において、辺 \(e\) が頂点 \(x\) とその親 \(p\) を結ぶ辺であるとき、辺 \(e\) を切ると \(x\) を根とする部分木 \(T_x\) に属するすべての頂点へ \(u\) から到達できなくなります。

したがって、辺 \(e = (p, x)\) を切ったときに、高橋君が \(u\) に侵入して得られるデータ量は、 $\(W_u - (\text{部分木 } T_x \text{ 内で、} u \text{ からの距離が } D \text{ 以下の頂点のデータ量総和})\)$ となります。

\(u\) から見て \(e\) の先（部分木 \(T_x\)）にない辺を切っても、\(u\) から \(S_u\) への到達性には影響しないため、獲得量は \(W_u\) のままです。

この性質を利用すると、\(u\) を始点とする1回の探索（BFS）だけで、すべての辺 \(e\) を切ったときに \(u\) 側で得られるデータ量をまとめて計算することができます。

---

アルゴリズム

各辺 \(i\) （\(A_i\) と \(B_i\) を結ぶ）に対して、以下の情報を管理します。 - max_val[i][0] : 辺 \(i\) を切ったときの、\(A_i\) 側のコンポーネントにおける高橋君の最大獲得量 - max_val[i][1] : 辺 \(i\) を切ったときの、\(B_i\) 側のコンポーネントにおける高橋君の最大獲得量

各頂点 \(u \in \{1, 2, \dots, N\}\) について、以下の手順を行います。

1. 最短距離の計算 (BFS) \(u\) を始点としてBFSを行い、すべての頂点への距離 dist を求めます。同時に、BFSでの探索順（トポロジカル順）と、各頂点の「親」を記録しておきます。

2. 初期値と重みの設定 \(u\) からの距離が \(D\) 以下の頂点 \(i\) に対して sum_val[i] = V[i] とし、それ以外の頂点は 0 とします。これらの総和 \(W_u\) を求めておきます。

3. 部分木の累積和をボトムアップに計算 BFSの探索順の逆順（葉から根の方向）に、子から親へ sum_val を累積します。 $\( \text{sum\_val}[\text{parent}] \leftarrow \text{sum\_val}[\text{parent}] + \text{sum\_val}[\text{child}] \)\( これにより、各頂点 \)x\( について、`sum_val[x]` は「\)x\( の部分木内にある、\)u\( からの距離が \)D$ 以下の頂点のデータ量総和」になります。

4. 各辺を切ったときの \(u\) 側コンポーネントの値を更新 各頂点 \(x\) （\(x \neq u\)）について、親 \(p\) と結ぶ辺 \(e\) （インデックスを \(idx\) とする）を切った場合を考えます。 このとき、\(u\) は \(p\) 側に属しているため、辺 \(idx\) の「\(p\) が属する側」の max_val[idx][side] を \(W_u - \text{sum\_val}[x]\) で最大化更新します。

すべての \(u\) について上記を繰り返した後、青木君の最適な戦略（獲得量の最小化）を求めます。 - 何も切らない場合の最大値 \(M_0 = \max_u W_u\) - 各辺 \(i\) を切った場合の最大値 \(\max(\text{max\_val}[i][0], \text{max\_val}[i][1])\)

これらすべての選択肢（\(N\) 通り）の中での最小値が答えとなります。

---

計算量

時間計算量: \(O(N^2)\)

• 各頂点 \(u\)（\(N\) 通り）について、
  • BFSによる距離と親の計算：\(O(N)\)
  • 葉から根へのボトムアップな累積和の計算：\(O(N)\)
  • 各辺に対する max_val の更新：\(O(N)\)
• したがって、全体の時間計算量は \(O(N^2)\) となります。\(N \le 3000\) では最悪でも約 \(9 \times 10^6\) 回のループとなり、実行時間制限（通常2.0秒）に対して十分に高速（数十ミリ秒程度）で動作します。

空間計算量: \(O(N)\)

• グラフの隣接リスト、各頂点への距離や親を保持する配列、および max_val 配列はすべてサイズ \(O(N)\) です。よって、空間計算量は \(O(N)\) となり、メモリ制限に対しても非常に軽量です。

---

実装のポイント

• BFSの探索順の再利用: 通常、部分木のボトムアップな計算にはDFS（深さ優先探索）の帰りがけ順などが使われますが、BFSでキュー（q）に追加された順の逆順（後ろから走査）を使用することで、追加のDFSをすることなく、トポロジカル順の逆順を \(O(N)\) で得ることができます。

• 辺の方向の判定: 辺 \(i\) を切った際、親 \(p\) が \(A_i\) と \(B_i\) のどちらであるかを判定して、max_val[idx][0] と max_val[idx][1] の適切な方を更新する必要があります。コード内では side = (p == A[idx] ? 0 : 1) としてこれをスマートに判定しています。

  ソースコード

#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;
}

---

この解説は gemini-3.5-flash-high によって生成されました。