PKU 1655-Balancing Act

問題概要

ノード数がN(<=20000)の木がある．
ある一つのノードを取り外すことで木を切断した時に残る複数の木の最大ノード数をバランスという．
バランスの最小値を求めよ

解法

木の根を入次数が1の頂点から適当に決める．
そうすると，それよりも深い部分の頂点の個数をO(E)で計算することが出来，それにより最終的な計算量もO(E)となる．

実装(C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int TCASE;
#define REP(i,x)for(int i=0;i<(int)x;i++)
vector<int> G[20000];
bool ac[20000];
int cnt[20000];
int ans=99999999;
int ansno=-1;
int dfs(int now,int back=-1){
	if(cnt[now]>0)return cnt[now];
	cnt[now]=1;
	REP(i,G[now].size()){
		if(G[now][i]!=back){
			cnt[now]+=dfs(G[now][i],now);
		}
	}
	return cnt[now];
}
int N;
void solve(int now,int back=-1){
	//ここで消してみる
	int tans=N-cnt[now];
	REP(i,G[now].size()){
		if(G[now][i]!=back){
			tans=max(tans,cnt[G[now][i]]);
		}
	}
	if(ans>tans){
		ans=tans;
		ansno=now;
	}else if(ans==tans&&ansno>now){
		ansno=now;
	}
	REP(i,G[now].size()){
		if(G[now][i]!=back){
			solve(G[now][i],now);
		}
	}
}
int main() {
	scanf("%d",&TCASE);
	while(TCASE--){
		scanf("%d",&N);
		REP(i,N)G[i].clear();
		REP(i,N-1){
			int a,b;
			scanf("%d%d",&a,&b);
			b--;a--;
			G[a].push_back(b);
			G[b].push_back(a);
		}
		int root=-1;
		REP(i,N){
			if(G[i].size()==1){
				root=i;break;
			}
		}
		ansno=-1;
		ans=99999999;
		fill(ac,ac+N,0);
		fill(cnt,cnt+N,0);
		dfs(root);
		solve(root);
		cout<<ansno+1<<" "<<ans<<endl;
	}
	return 0;
}