Shorten Diameter [AGC 001 : C]

問題

http://agc001.contest.atcoder.jp/tasks/agc001_c

N頂点の木がある。
この木の直径をK以下にするために削除する必要がある頂点数の最小値は？

2 <= N <= 2*10^3
1 <= K <= N-1

帰納的考察(Editorial見た)

1. 木の直径を使った問題は初めてだったので、無理かなと思ってDに逃げた
2. (Dもダメでしたが)
3. 木を使う問題だったので、DFSかなとも思ったが、O(N)だと条件が若干緩すぎる
4. むむむ

――壁――

5. 木の直径に関する性質がある

木の直径をDとする

• Dが偶数 : 木の中心となるある頂点が存在し、そこから他頂点への距離がD/2以下
• Dが奇数 : 木の中心となるある辺が存在し、その端点から他頂点への距離が(D-1)/2以下

6. 今回の問題はO(N^2)でも間に合う問題なので、木の中心を全て試しても間に合う（なるほど！）
7. Dが偶数なら頂点、Dが奇数なら辺の端点の距離を0として、そこからDFSする -> dfs()
8. あとは、D/2か(D-1)/2より大きい頂点を数えて、その最小値を答えれば答え

実装

http://agc001.contest.atcoder.jp/submissions/809970

int N, K;
vector<int> E[2000];
//-----------------------------------------------------------------
int dep[2000];
void dfs(int i) {
	for (int j : E[i]) if (dep[j] < 0) {
		dep[j] = dep[i] + 1;
		dfs(j);
	}
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> K;
	rep(i, 0, N - 1) {
		int A, B; cin >> A >> B;
		A--; B--;
		E[A].push_back(B);
		E[B].push_back(A);
	}
 
	int ans = N;
	if (K % 2 == 0) {
		rep(i, 0, N) {
			rep(j, 0, N) dep[j] = -1;
			dep[i] = 0;
			dfs(i);
 
			int cnt = 0;
			rep(j, 0, N) if (K / 2 < dep[j]) cnt++;
			ans = min(ans, cnt);
		}
	}
	else {
		rep(i, 0, N) for (int j : E[i]) if (i < j) {
			rep(k, 0, N) dep[k] = -1;
			dep[i] = dep[j] = 0;
			dfs(i);
			dfs(j);
 
			int cnt = 0;
			rep(k, 0, N) if ((K - 1) / 2 < dep[k]) cnt++;
			ans = min(ans, cnt);
		}
	}
 
	cout << ans << endl;
}