Codeforces ECR #007 : E. Ants in Leaves

きづけて良かった。でも凡ミスしなければ１位取れたのになぁ。
http://codeforces.com/contest/622/problem/E

問題

根付き木が与えられる。
各葉には蟻がいる。

時間１毎に、各蟻は親頂点に移動できる（しなくても良い）。
ただし、根以外の頂点は１頂点に複数の蟻が同時に存在してはならない。

全ての蟻が根に移動するのにかかる最短時間を求めよ。

回答

各頂点で蟻が詰まる様子をシミュレートするのは面倒なので省略したい。
実際は根に近づくほど余計詰まることになる。
そこで一番詰まりやすい根の１つ手前の頂点でのみどれだけ詰まるか考えればよい。

根の１つ子の頂点について、SubTree内に現れる頂点の深さを列挙する。
それらをソートして、時間ごとに１匹ずつ蟻が根に移動すると考え、全部の蟻が根に移動しきるまでの最短時間を求めるとよい。

int N;
vector<int> E[505050];
vector<int> H[505050];
int SL;


void dfs(int cur,int pre,int d) {
	
	if(pre==0) SL=cur;
	
	if(cur && E[cur].size()==1) H[SL].push_back(d);
	FORR(r,E[cur]) if(r!=pre) dfs(r,cur,d+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	dfs(0,-1,0);
	
	int ma=0;
	FOR(i,N) if(H[i].size()) {
		int last=0;
		sort(ALL(H[i]));
		FORR(r,H[i]) last=max(r,last+1);
		ma=max(ma,last);
	}
	
	cout<<ma<<endl;
	
}

まとめ

根の一つ子の頂点だけ考えればよい、と気づけるかが鍵。