概要

木構造の通信ネットワークで、青木君が辺を高々 \(1\) 本切ったあと、高橋君が最も得をする侵入先を選びます。
各辺を切った場合に「高橋君が取れる最大値」を効率よく求め、その中の最小値を答えます。

考察

青木君が辺を \(1\) 本切ると、木は \(2\) つの連結成分に分かれます。
高橋君は切断後の連結成分のどちらかにある頂点を侵入先として選び、その頂点から距離 \(D\) 以下で到達できる頂点のデータを盗みます。

素朴には、

• 青木君が切る辺を全通り試す：\(O(N)\)
• 高橋君の侵入先を全通り試す：\(O(N)\)
• そのたびに距離 \(D\) 以下の頂点を探索する：\(O(N)\)

となり、全体で \(O(N^3)\) かかります。
\(N \leq 3000\) なので、これは間に合いません。

そこで、発想を逆にします。

「各切断辺について高橋君の最適値を求める」のではなく、
「各侵入先 \(x\) について、すべての切断辺に対する結果をまとめて更新する」ことを考えます。

---

木を適当な頂点、ここでは頂点 \(0\) を根として根付き木にします。
根付き木にすると、根以外の各頂点 \(c\) は、親との辺 \((parent[c], c)\) に対応します。

この辺を切ると、木は次の \(2\) つに分かれます。

• 頂点 \(c\) を根とする部分木
• それ以外の部分

ここで、侵入先を \(x\) とします。

まず、辺を切らなかった場合に、\(x\) から距離 \(D\) 以下にある頂点のデータ合計を \(B_x\) とします。

また、頂点 \(c\) の部分木の中にあって、かつ \(x\) から距離 \(D\) 以下にある頂点のデータ合計を \(S_x(c)\) とします。

辺 \((parent[c], c)\) を切った場合、

• \(x\) が \(c\) の部分木内にあるなら、盗めるのは \(S_x(c)\)
• \(x\) が \(c\) の部分木外にあるなら、盗めるのは \(B_x - S_x(c)\)

です。

なぜなら、切断された辺をまたいだ先には行けなくなるためです。
同じ連結成分内の距離は、元の木での距離と変わりません。

したがって、各辺 \(c\) について、

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

が、その辺を切ったときに高橋君が盗める最大値です。

青木君はこの値を最小化したいので、全ての辺について最小を取ります。
また、青木君は「切らない」ことも選べるので、その場合の値

\[ \max_x B_x \]

も候補に含めます。

アルゴリズム

1. 木を頂点 \(0\) を根として根付き木にする。
2. DFS により以下を求める。
   • parent[v]: 頂点 \(v\) の親
   • children[v]: 頂点 \(v\) の子
   • tin[v], tout[v]: Euler Tour による部分木判定用の時刻
   • order: DFS 順

Euler Tour を使うと、頂点 \(x\) が頂点 \(c\) の部分木内にあるかは

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

で判定できます。

1. 各侵入先 \(x\) について以下を行う。

   1. \(x\) から距離 \(D\) 以下の頂点を DFS/BFS で求める。
   2. 各頂点 \(u\) について、距離 \(D\) 以下なら \(V_u\)、そうでなければ \(0\) とする。
   3. 根付き木の下から順に部分木和を計算する。

   sub[c] は、

   $\( S_x(c) \)$

   すなわち「頂点 \(c\) の部分木内にあり、かつ \(x\) から距離 \(D\) 以下の頂点のデータ合計」になります。

   1. sub[0] が、切断しない場合に \(x\) から盗める合計 \(B_x\) です。 これを使って noCut を更新します。

   2. 各切断候補の辺、つまり根以外の頂点 \(c\) について更新します。

      • \(x\) が \(c\) の部分木内なら

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

      • \(x\) が \(c\) の部分木外なら

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

2. 最後に、各辺 \(c\) について

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

を計算します。

これは、その辺を切ったときに高橋君が最適に侵入先を選んだ場合の盗める最大値です。

1. 「切らない場合」の noCut と、各辺を切る場合の値の最小値を答えます。

計算量

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

各侵入先 \(x\) について、距離計算、部分木和計算、各辺の更新をそれぞれ \(O(N)\) で行います。
侵入先は \(N\) 通りあるため、全体で \(O(N^2)\) です。

実装のポイント

• 各辺は、根付き木における「子側の頂点 \(c\)」で表します。

  • 辺 \((parent[c], c)\) を切る、という意味です。

• 部分木判定には Euler Tour の tin, tout を使います。

• sub[c] は、固定した侵入先 \(x\) に対する部分木内の盗めるデータ合計です。

• 値 \(V_i\) は最大 \(10^9\)、合計は最大で \(3 \times 10^{12}\) 程度になるため、long long を使う必要があります。

• 距離探索では、距離が \(D\) に達したらそれ以上先へ進まないことで無駄な探索を避けています。

  ソースコード

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

---

この解説は gpt-5.5-high によって生成されました。