概要

木構造のネットワーク上で、青木君が「高々 1 本の辺を切る」ことで高橋君の利得を最小化し、高橋君が「ある頂点から距離 \(D\) 以内の頂点のデータ合計」を最大化する、ミニマックス（最小化と最大化）ゲームの値を求める問題です。

考察

ゲームの構造

このゲームは手番が決まったミニマックスです。

• 青木君の行動は 「辺を切らない」または「\(N-1\) 本のどれか 1 本を切る」 の合計 \(N\) 通り。
• 各行動に対して、高橋君は 頂点 \(v\) を選んで「\(v\) から距離 \(D\) 以内のデータ合計」を最大化 します。

したがって求める答えは、

\[ \min_{\text{青木の行動}} \left( \max_{v} \big(\text{$v$ から距離 $D$ 以内のデータ合計}\big) \right) \]

です。「切らない場合の最大利得」と「各辺を切った場合の最大利得」をすべて求め、その中で最小のものが答えになります。

素朴なアプローチの問題点

「青木君の行動 \(N\) 通り × 高橋君の頂点 \(N\) 通り × 各頂点から距離 \(D\) 以内の探索 \(O(N)\)」と単純に計算すると \(O(N^3)\) となり、\(N \le 3000\) では約 \(2.7 \times 10^{10}\) 回となって間に合いません。

解決のアイデア

ポイントは 高橋君の選ぶ頂点 \(v\) を固定して、木を \(v\) を根として考える ことです。こうすると「どの辺を切るか」を 1 回の探索でまとめて処理できます。

\(v\) を根として BFS し、各頂点 \(x\) の深さ（\(v\) からの距離）を求めます。ここで

\[ \text{subval}[x] = \sum_{\substack{y \in (\text{$x$ を根とする部分木})\\ \text{dist}(v,y)\le D}} V[y] \]

と定義します。これは「\(x\) を根とする部分木の中で、\(v\) から距離 \(D\) 以内に入る頂点のデータ合計」です。葉から根に向かって足し上げることで \(O(N)\) で全頂点分計算できます。

このとき:

• 辺を切らないときの \(v\) の利得 は \(f = \text{subval}[v]\)（木全体で距離 \(D\) 以内のデータ合計）。
• 頂点 \(x\) の親への辺 \(e\) を切ったときの \(v\) の利得 は、\(x\) 以下の部分木が \(v\) から切り離されるため

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

となります（距離 \(D\) 以内で失われるのはちょうど \(\text{subval}[x]\) 分）。

辺 \(e\) は必ず木の辺なので、根を \(v\) とすると常に「親側の頂点」と「子側の頂点 \(x\)」に分かれます。よって 1 回の BFS で、\(v\) を中心に選んだときの「切らない場合」「各辺を切った場合」すべての利得が同時に求まります。

アルゴリズム

各頂点 \(v = 1,2,\ldots,N\) について以下を行います。

1. \(v\) を根として BFS し、各頂点の深さ・親・親への辺番号を求める。
2. 各頂点 \(x\) について \(\text{subval}[x]\) を初期化（距離 \(D\) 以内なら \(V[x]\)、そうでなければ \(0\)）し、BFS 順の逆順で親に足し上げる。
3. \(f = \text{subval}[v]\) を「切らない場合」の候補として noCut の最大値を更新。
4. 各頂点 \(x\)（\(v\) 以外）について、親への辺 \(e\) を切ったときの利得 \(f - \text{subval}[x]\) で \(M[e]\)（辺 \(e\) を切ったときの最大利得）を更新。

最後に

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

を出力します。noCut は「辺を切らない」という青木君の選択肢に、\(M[e]\) は「辺 \(e\) を切る」選択肢にそれぞれ対応し、その最小値を青木君が選びます。

計算量

• 時間計算量: \(O(N^2)\)（各頂点を中心とした BFS と足し上げが \(O(N)\)、それを \(N\) 回）
• 空間計算量: \(O(N)\)（隣接リストや作業配列）

\(N \le 3000\) なので \(O(N^2) \approx 9 \times 10^6\) となり、十分高速です。

実装のポイント

• BFS の訪問順序 order を保持しておき、その逆順に親へ加算することで、再帰を使わずに部分木和を計算できます（スタックオーバーフロー回避にも有効）。

• データ量は最大 \(10^9\)、頂点数最大 \(3000\) なので合計は最大 \(3 \times 10^{12}\) となり、long long（64bit 整数）が必須です。

• 「辺 \(e\) を切ったときの最大利得 \(M[e]\)」は すべての中心 \(v\) にわたる最大値 であることに注意してください。最後に青木君がその中から最小を選ぶ、という二段構えの最適化になっています。

  ソースコード

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

---

この解説は claude4.8opus-high によって生成されました。