AGC001 C - Shorten Diameter
問題
n頂点の木が与えられる
この木の直径をk以下にするために削除する必要のある頂点数の最小値を求める
2 <= n <= 2000
解法
木の直径をDとすると、
Dが偶数のとき) ある頂点vが存在し、vから他の頂点への距離がD/2以下となる
Dが奇数のとき) ある辺eが存在し、eから他の頂点への距離が(D-1)/2以下となる
vとeは木の中心と呼ばれる
この木の性質を使う
ある頂点[辺]を中心と定めると、木の直径をk以下にするためには、中心からの距離がk/2を超える点を全て消す必要がある
kの偶奇で場合分けして、それぞれ全ての点/辺を中心にしてみればいい
O(n^2)
考えてみればそれはそうなんだけどこの性質は知らなかった
覚えておこう😤
int n, k, a[2020], b[2020], d[2020], res = inf; vector<int> e[2020]; void rec(int v) { each(i,e[v]) if (d[i]==-1) d[i] = d[v]+1, rec(i); } void ev() { rep(i,n) { rep(j,n) d[j] = -1; d[i] = 0; rec(i); int cnt = 0; rep(j,n) if (d[j]>k/2) cnt++; chmin(res, cnt); } } void od() { rep(i,n-1) { rep(j,n) d[j] = -1; d[a[i]] = d[b[i]] = 0; rec(a[i]), rec(b[i]); int cnt = 0; rep(j,n) if (d[j]>k/2) cnt++; chmin(res, cnt); } } signed main() { cin >> n >> k; rep(i,n-1) { cin >> a[i] >> b[i]; a[i]--, b[i]--; e[a[i]].push_back(b[i]), e[b[i]].push_back(a[i]); } if (k%2==0) ev(); else od(); cout << res << endl; }