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