Codeforces #510 Div2 F. Leaf Sets

割と典型寄りかな。
http://codeforces.com/contest/1042/problem/F

問題

木を成す無向グラフが与えられる。
葉頂点をいくつかのグループに分けたい。
ただしグループ内の葉の距離はK以下でなければならない。

最小でグループをいくつ構築すればよいか。

解法

葉から順に、各頂点のSubTree内でグループ未構築の葉の距離の最大値を求めていこう。
なお、SubTree内の葉がすべてグループを構築済みの場合、そのような葉は無しとみなす。

ある頂点の子頂点のSubTree内で、葉までの距離の和がKを超える場合それらはグループになりえない。
よってそのような場合遠い方の葉は単独でグループを構築したとみなし、その子頂点は以後無視する。
和がKを超えない範囲では葉が何個あってもよく、以後最遠の点のみ考えればよいので、「グループ未構築の葉の距離の最大値」だけを管理していけばよい。

int N;
vector<int> E[1010101];
int D[1010101];
int ret=0;
int K;
vector<int> Ds[1010101];

int dfs(int cur,int pre,int d) {
	D[cur]=d;
	if(E[cur].size()==1) {
		return d;
	}
	FORR(e,E[cur]) if(e!=pre) {
		int a=dfs(e,cur,d+1);
		if(a>=0) Ds[cur].push_back(a);
	}
	sort(ALL(Ds[cur]));
	
	while(Ds[cur].size() && Ds[cur].back()-d>=K) {
		ret++;
		Ds[cur].pop_back();
	}
	
	while(Ds[cur].size()>=2 && Ds[cur][Ds[cur].size()-2]+Ds[cur][Ds[cur].size()-1]-2*d>K) {
		ret++;
		Ds[cur].pop_back();
	}
	if(Ds[cur].empty()) return -1;
	return Ds[cur].back();
	
}

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) if(E[i].size()>=2) break;
	
	if(dfs(i,i,0)>=0) ret++;
	cout<<ret<<endl;
}

まとめ

今回もDiv2 Fの割には簡単。