Codeforces 321C Ciel the Commander

問題

n頂点からなる木が与えられる。
木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。

同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも
小さいアルファベットのラベルを持つ頂点が存在する。

このような割り当てが存在するなら、そのような割り当てをどれか一つ具体的に出力せよ。
そうでない場合はImpossible!と出力せよ。

制約条件

n≦10000

方針

まず、明らかにAのラベルは一つしかおくことができない。
Aのラベルを置いたノードを取り除くと、木はいくつかのサブツリーに分かれる。
そのサブツリーで、今度は最も大きいラベルをBとして同じ問題を解けばよい。

ではどの頂点にAのラベルを貼るかであるが、これは木のcentroidに貼れば十分。
木のcentroidとは、その頂点を木から取り除いた際に、
できるサブツリーのうち最大のもののサイズが最も小さくなるような頂点。

centroidを選び続けていくと、その度に木のサイズは半分になるので、
n≦10^5から、分割を20回もしないうちにサイズが1になり、
結局全ての場合にラベルが貼れることがわかる。

centroidは適当に求める。
毎回木DPをしてOKだが、初期化を全部やってしまうとO(n^2)かかってしまうので、
サブツリーの要な部分だけを初期化するようにすればＯＫ．
これで計算量はO(n logn)のはず。

ソースコード

int n, num[100000];
vector<vi> e;
char ans[100000];

void init(int c, int p){
	num[c] = 1;
	rep(i, e[c].size()) if(e[c][i] != p && !ans[e[c][i]]){
		init(e[c][i], c);
		num[c] += num[e[c][i]];
	}
}
pi centroid(int c, int p, int n){
	pi res(n - num[c], c);
	rep(i, e[c].size()) if(e[c][i] != p && !ans[e[c][i]]) res.first = max(res.first, num[e[c][i]]);
	rep(i, e[c].size()) if(e[c][i] != p && !ans[e[c][i]]) res = min(res, centroid(e[c][i], c, n));
	return res;
}

void rec(int c, char ch){
	init(c, c);
	pi p = centroid(c, c, num[c]);
	c = p.second;
	ans[c] = ch;
	rep(i, e[c].size()) if(!ans[e[c][i]]) rec(e[c][i], ch + 1);
}

int main(){
	cin >> n;
	e.resize(n);
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].pb(b);
		e[b].pb(a);
	}
	rec(0, 'A');
	rep(i, n) cout << ans[i] << (i == n - 1 ? "\n" : " ");
	
	return 0;
}