## 2013年9月1日日曜日

### Codeforces Round #190 Ciel the Commander

ソースコード
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)
#define MP(x,y) make_pair(x,y)

int N;
vector<int> edge[100000];
int rank[100000];
int size[100000];
bool cut[100000];

// get the number of nodes in the subset a node v belong to.
void getSize(int v, int par = -1) {
size[v] = 1;
REP (i, edge[v].size()) {
int w = edge[v][i];
if (w == par || cut[w]) continue;
getSize(w, v);
size[v] += size[w];
}
}

// select an optimal root node from the subset a node v belong to.
pair<int, int> chooseRoot(int v, int par, int total) {
pair<int, int> ret = MP(1<<30, -1);

int rm = total;
int sub = 0;
REP (i, edge[v].size()) {
int w = edge[v][i];
if (w == par || cut[w]) continue;
ret = min(ret, chooseRoot(w, v, total));
sub = max(sub, size[w]);
rm -= size[w];
}
sub = max(sub, rm);
ret = min(ret, MP(sub, v));
return ret;
}

void dfs(int v, int depth) {
getSize(v);
int r = chooseRoot(v, -1, size[v]).second;
rank[r] = depth;
cut[r] = true;
REP (i, edge[r].size()) {
int w = edge[r][i];
if (cut[w]) continue;
dfs(w, depth+1);
}
}

int main() {
cin >> N;
REP (i, N-1) {
int a, b;
cin >> a >> b;
edge[--a].push_back(--b);
edge[b].push_back(a);
}

dfs(0, 0);

REP (i, N) {
char c = 'A' + rank[i];
putchar(c);
putchar(' ');
}
puts("");

return 0;
}