読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AGC001 C - Shorten Diameter

AtCoder

現時点で正しいと思う理解の仕方を書いたので、間違いや気になるところがあればぜひ教えてください。

問題

C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder

 N 頂点の木がある。この木の直径を  K 以下にするために削除する必要のある最小の頂点数を求めよ。ただし頂点を削除した後のグラフは連結でなければならない。

制約

 2 \leq N \leq 2000

解法

 D が偶数のときを説明します。*1

解説にある通り、以下の定理が成り立ちます。(この記事では既知としますが、要望があれば証明を書きます。)

直径が  D 以下  \Rightarrow \exists v, \ \forall u, \ d_{uv} \leq D / 2

ただし、 d_{uv} = 頂点 u から頂点 v への最短距離 = u から v へのパスに含まれる辺の本数 です。

制約より  O(N^2) の解法が通るので、定理右側の  v を全探索します。 v を決めると、必要性より  d_{uv} > D / 2 なる頂点  u はすべて削除しなければなりません。

逆に、そのような  u をすべて削除して得られたグラフ  G' が、実際に直径  D 以下の連結な木となることを示します。操作の方法から連結な木となることは明らかでしょう。では直径についてです。 G' において、 v (定理右側のアレ) を根として  z = lca(x, y) とします。すると  G' の頂点集合に含まれる任意の  x, y について  d_{xy} = d_{vx} + d_{vy} - 2 d_{vz} \leq d_{vx} + d_{vy} \leq (D / 2) + (D / 2) = D です。これで十分性が示せました。

まとめると、 D が偶数のときは、 v を全探索し、 d_{uv} > D / 2 なる  u の個数の最小値を更新していくことで答えを求めることができます。計算量は  O(N^2) です。

 D が奇数のときは 定理右側の  v が 辺になりますが、ほぼ同様に解けます。

以下のコードでは  v からの距離が  D / 2 以下の頂点を数えて  N から引いています。

#include <bits/stdc++.h>
using namespace std;
#define int long long   // <-----!!!!!!!!!!!!!!!!!!!

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define all(a) (a).begin(),(a).end()

typedef long long ll;
typedef pair<int, int> Pii;
typedef tuple<int, int, int> TUPLE;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
typedef vector<vector<int>> Graph;
const int inf = 1e9;
const int mod = 1e9 + 7;

int N, K;
Graph G;

int dfs(int v, int pre, int d) {
    if (d < 0) return 0;
    int ret = 1;
    for (auto&& nxt : G[v]) {
        if (nxt != pre) {
            ret += dfs(nxt, v, d - 1);
        }
    }
    return ret;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> N >> K;
    G.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }

    int alive = -1;
    if (K % 2 == 0) {
        rep(i, N) {
            alive = max(alive, dfs(i, -1, K / 2));
        }
    } else {
        rep(i, N) {
            for (auto&& j : G[i]) {
                alive = max(alive, dfs(i, j, (K - 1) / 2) + dfs(j, i, (K - 1) / 2));
            }
        }
    }

    cout << N - alive << endl;
}

*1:すみません、書いたあとで気づいたんですけどこれはKです