AtCoder AGC #001 : C - Shorten Diameter

Dで手間取って微妙な成績でした。
http://agc001.contest.atcoder.jp/tasks/agc001_c

問題

N頂点の木を成す無向グラフが与えられる。
ここからないくつか頂点を消し、直径K以下にしたい。
最少でいくつの頂点を消せばよいか。

解法

色々な解法がありそうな問題。
自分は各頂点からKを超えた距離の頂点の数を数え、それらが多い順に頂点を消したところうまく行った。

int N,K;
vector<int> E[2020];
int num[2020];
vector<int> S[2020];

void dfs(int id,int cur,int pre,int d) {
	if(d>K) S[id].push_back(cur), num[id]++;
	FORR(r,E[cur]) if(r!=pre) dfs(id,r,cur,d+1);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	FOR(i,N) dfs(i,i,-1,0);
	int del=0;
	FOR(i,2020) {
		int ma=0;
		FOR(x,N) if(num[x]>num[ma]) ma=x;
		if(num[ma]==0) break;
		FORR(r,S[ma]) if(num[r]>0) num[r]--;
		num[ma]=0;
		del++;
	}
	
	cout<<del<<endl;
}

まとめ

スマートな解は何だろうな。