centroides-1.cpp

#include <iostream>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

#define graph vector<set<int> >

int tree_size(int s, int parent, graph &G) {
	int count = 1;
	for(int t : G[s])
	if(t != parent) {
		count += tree_size(t, s, G);
	}
	return count;
}

tuple<int, int> scentroid(int s, int parent, graph &G, int n) {
	int cent_ret = s;
	int count = 1;

	for(int t : G[s]) {
		if(t != parent) {
			int cent_t, count_t;
			tie(cent_t, count_t) = scentroid(t, s, G, n);

			if(count_t > (n/2)) {
				cent_ret = cent_t;
			}
			count += count_t;
		}
	}
	return make_tuple(cent_ret, count);
}

int centroid(int s, graph &G) {
	int cent, count;
	tie(cent, count) = scentroid(s, -1, G, tree_size(s, -1, G));
	return cent;
}

int make_gc(int s, graph &G, graph &G_c) {
	int cent = centroid(s, G);
	set<int> fils;
	for(int t : G[cent]) fils.insert(t);
	
	for(int t : fils) {
		G[t].erase(cent);
		G[cent].erase(t);

		int tc = make_gc(t, G, G_c);
		G_c[tc].insert(cent);
		G_c[cent].insert(tc);
//		cout << "#" << tc << "<->" << cent << endl;
	}
	return cent;
}

void etiquetter(int s, int parent, graph &G, vector<char> &etiquettes, int profondeur) {
	etiquettes[s] = 'A' + profondeur;
	for(int t : G[s])
	if(t != parent) {
		etiquetter(t, s, G, etiquettes, profondeur+1);
	}
}

int main() {
	int N;
	cin >> N;

	graph G(N);
	int s, t;
	for(int i=0 ; i < N-1 ; i++) {
		cin >> s >> t;
		s--; t--;
		G[s].insert(t);
		G[t].insert(s);
	}

	graph Gc(N);
	int racine = make_gc(0, G, Gc);

	vector<char> etiquettes(N);
	etiquetter(racine, -1, Gc, etiquettes, 0);
	for(int i=0 ; i < N ; i++) {
		cout << etiquettes[i] << " ";
	}
	cout << endl;
}

// http://codeforces.com/contest/321/problem/C