Codeforces #190 Div1. C. Ciel the Commander

これは本番中に解けなかったが、直後にTwitterなどで「重心分解じゃね？」と聞いてわかった問題。
http://codeforces.com/contest/321/problem/C

問題

木構造のグラフが与えられる。
各点に以下の条件を満たすようA～Zのランクを割り当てよ。

• Aが最上位で、Zが最下位。
• 同ランクの点を最短距離で移動する場合、必ず1個はより上位ランクの点を経由する。

解法

まず1列にランク未割当の点が並んでいる場合を考える。

**************

このとき、真ん中に最上位ランクAを置いてみる。

******A*******

Aの両側にBを1つずつ置けば、B同士は題意を満たす。この時、Bを未割当の一連の点の真ん中に2つ配置する。

B***A***B***

次に、同様に各一連の未割当点の真ん中にCを配置する。

B*C*A*C*B*C*

最後にDを置くとDCDBDCDADCDBDCDで答えになる。つまり、列の中点に未割当の最上位ランク点を置く、という処理を再帰的に行えばよい。

実際は点が1列に並ぶとは限らないが、この手法は木でも応用できる。
また、1回毎に木を半分以下の大きさの木に分割するなら、点が10^6個あっても20種類のランクで2^20個に木を分割できる。

なお、この木のサイズを元の半分以下に分割する手法としては重心分解がある。
これは蟻本に載っている。
木の任意の点から始め、サブツリーの点の数が半分以上となる点の方向に順次移動していく。
すべてのサブツリーの点が半分以下となるならそこは重心であり、最上位ランクを割り当てればよい。

int N;
vector<int> E[100001];
char C[100001];
int num[100001];
char CN[100001];

int dfs_num(int cur,int pre) {
	int i;
	int ma=-1;
	
	num[cur]=1;
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre) continue;
		if(C[tar]) CN[cur] = max(CN[cur],C[tar]);
		else num[cur]+= dfs_num(tar,cur), CN[cur] = max(CN[cur],CN[tar]);
	}
	return num[cur];
}

pair<int,int> dfs_center(int cur,int pre,int nu) {
	int i;
	pair<int,int> res=make_pair(1<<30,-1);
	int ma=0,c=1;
	
	FOR(i,E[cur].size()) {
		int tar=E[cur][i];
		if(tar==pre || C[tar]) continue;
		res=min(res,dfs_center(tar,cur,nu));
		
		ma=max(ma,num[tar]);
		c+=num[tar];
	}
	return min(res,make_pair(max(ma,nu-c),cur));
}

void solve() {
	int r,i,j,k,l,x,y,tx,ty;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	
	FOR(i,N) {
		while(C[i]==0) {
			dfs_num(i,-1);
			pair<int,int> p=dfs_center(i,-1,num[i]);
			C[p.second] = CN[i]+1;
			if(C[p.second]==1) C[p.second]='A';
			if(p.first==0) break;
		}
	}
	FOR(i,N) _P("%c ",C[i]);
	_P("\n");
}

まとめ

重心分解を最初から知っていれば本番中に解けたが…蟻本を見直さなきゃだめだね。