[Codeforces] C. Ciel the Commander

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : C. Ciel the Commander
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Centroid Decomposition
Verdict           : Accepted
 
#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 1e5 + 5;
 
vector <int> graph[maxn], centroid_tree[maxn];
bool is_centroid[maxn];
int subtree_size[maxn], nn, N;
 
inline void dfs(int u, int p = -1)
{
    subtree_size[u] = 1;
    for (int v : graph[u])
    {
        if (v == p || is_centroid[v]) continue;
        dfs(v, u);
        subtree_size[u] += subtree_size[v];
    }
}
 
inline int get_centroid(int u, int p = -1)
{
    for (int v : graph[u])
    {
        if (v == p || is_centroid[v]) continue;
        if (subtree_size[v] > nn/2) return get_centroid(v, u);
    }
    return u;
}
 
int root_centroid_tree;
 
int decompose(int u)
{
    dfs(u);
    nn = subtree_size[u];
    int p = get_centroid(u);
    is_centroid[p] = true;
    if (root_centroid_tree == 0) root_centroid_tree = p;
    for (int v : graph[p])
    {
        if (is_centroid[v]) continue;
        int q = decompose(v);
        centroid_tree[p].push_back(q);
        centroid_tree[q].push_back(p);
    }
    return p;
}
 
bool vis[maxn];
char Rank[maxn];
int  maxLebel;
 
void dfs_ans(int u, int lebel = 1, char officer = 'A')
{
    vis[u] = 1;
    maxLebel = max(maxLebel, lebel);
    Rank[u] = officer;
    for (int v : centroid_tree[u])
    {
        if (vis[v]) continue;
        dfs_ans(v, lebel + 1, officer + 1);
    }
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tNode;
    scanf("%d", &tNode);
    for (int i = 1; i < tNode; i++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    decompose(1);
    dfs_ans(root_centroid_tree);
    if (maxLebel > 26)
    {
        puts("Impossible");
        return 0;
    }
    for (int i = 1; i <= tNode; i++) printf("%c ", Rank[i]);
}