喵~！指挥官大人，下午好呀！Ciel a.k.a. 本喵，又来为您解决棘手的难题啦！这次的任务是在树之国部署军官，听起来就很有趣对不对？让本喵来带您一步步分析，保证您能轻松搞定，的说！

题目大意

首先，我们来理解一下任务目标是什么，喵~

在一个叫做“树之国”的地方，有 n 座城市和 n-1 条道路。这些城市和道路构成了一棵树的结构，也就是说，从任何一个城市出发，都能到达其他任何一个城市，而且路径是唯一的，捏。

我们的任务是给每一座城市都指派一名军官。军官有不同的军衔，从最高的 'A' 到 'Z'，总共 26 个等级。

但是，有一个非常重要的规则必须遵守： 如果两座不同的城市 x 和 y 的军官军衔相同，那么在 x 到 y 的唯一简单路径上，必须存在至少一个城市 z，其军官的军衔比他们要高。

简单来说，就是相同军衔的军官之间，必须由一个更高级别的上司来“监视”他们之间的通信路径，喵。

我们需要给出一个可行的军官分配方案。如果不存在这样的方案，就输出 "Impossible!"。

举个例子，如果城市 1 是 'A'，城市 2、3、4 都是 'B'，那么任何两个 'B' 级军官（比如 2 和 3）之间的路径 2-1-3 上，都有一个 'A' 级军官（在城市 1）。这样就是合法的，喵！

---

题解方法

看到这种在树上处理路径限制的问题，本喵的直觉就告诉我，这很可能和“分治”思想有关，捏！

让我们来仔细看看这个核心规则：同级被高级隔开。

这启发了我们一个绝妙的点子：

1. 我们可以在整棵树里找到一个“中心点”。
2. 给这个中心点分配最高的军衔 'A'。
3. 然后，我们把这个中心点从树上“拿走”。这样一来，整棵树就会分裂成好几个互不连通的小子树。

现在神奇的事情发生了！对于任意两个位于 不同 子树中的节点，它们之间的路径必然要经过我们刚才选定的那个 'A' 级军衔的中心点。这意味着，我们可以在这些不同子树里，放心地使用比 'A' 低一级的军衔 'B'，而不用担心它们之间会违反规则，因为 'A' 已经把它们完美地隔开了，喵~

对于每个分裂后的小子树，我们可以用同样的方法来处理：在小子树里找到一个新的“中心点”，给它分配次一级的军衔 'B'，然后再把它“拿走”，让这个小子树继续分裂……

这个过程不断重复下去，每次都用更低一级的军衔。'A' -> 'B' -> 'C' ...

这个“中心点”到底是什么呢？在树论中，它有一个响当当的名字——树的重心！

树的重心 (Centroid) 有一个非常棒的性质：把它从树上移除后，分裂出的所有子树中，最大的那个子树的大小也不会超过原树大小的一半。这个性质保证了我们递归的深度最多是 log(n) 级别。因为 n 最大是 10^5，log(10^5) 大约是 17，而我们有 26 个军衔可以用，所以军衔是绰绰有余的！这也意味着，一个可行的方案总是存在的，我们不需要考虑 "Impossible!" 的情况。

所以，我们的算法就是 树的重心分解 (Centroid Decomposition)：

1. 找到当前树（或子树）的重心。
2. 给这个重心分配当前递归深度对应的军衔（'A', 'B', 'C', ...）。
3. 将该重心标记为“已处理”。
4. 对剩下的每一个连通子树，递归地执行上述过程，并将军衔等级加一。

这样就能构造出一种绝对符合要求的方案啦，喵哈哈！

---

题解代码解析

下面让我们看看这份聪明的代码是如何实现这个想法的吧，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

const int MAXN = 100005;
std::vector<int> adj[MAXN]; // 邻接表，用来存树的结构捏
bool deleted[MAXN];         // 标记一个节点是不是已经被当做重心处理过了
int sz[MAXN];               // 存储子树的大小
char ans[MAXN];             // 存储每个城市的最终军衔
int n;

// 声明一下函数，这样 main 才能找到它们
void calc_sz(int u, int p);
int find_centroid(int u, int p, int comp_size);
void decompose(int u, char rank);

/**
 * @brief 计算当前连通块中，以 u 为根的子树大小
 * @param u 当前节点
 * @param p 父节点，防止往回跑
 */
void calc_sz(int u, int p) {
    sz[u] = 1; // 自己的大小是 1
    for (int v : adj[u]) {
        // 只遍历那些没被处理过、也不是父节点的邻居
        if (v != p && !deleted[v]) {
            calc_sz(v, u);
            sz[u] += sz[v]; // 加上子树的大小
        }
    }
}

/**
 * @brief 寻找当前连通块的重心
 * @param u 当前开始寻找的节点
 * @param p 父节点
 * @param comp_size 当前连通块的总大小
 */
int find_centroid(int u, int p, int comp_size) {
    for (int v : adj[u]) {
        // 如果某个子树 v 的大小超过了总大小的一半
        // 那么重心一定在那个“过重”的子树里，赶紧进去找！
        if (v != p && !deleted[v] && sz[v] * 2 > comp_size) {
            return find_centroid(v, u, comp_size);
        }
    }
    // 如果所有子树都不超过总大小的一半，那说明 u 就是重心啦！
    return u;
}

/**
 * @brief 核心的重心分解递归函数
 * @param u 递归入口节点
 * @param rank 当前要分配的军衔
 */
void decompose(int u, char rank) {
    // 1. 计算当前连通块的大小，为找重心做准备
    calc_sz(u, 0);
    int comp_size = sz[u];

    // 2. 找到这个连通块的重心
    int centroid = find_centroid(u, 0, comp_size);

    // 3. 给重心分配军衔，并标记为已处理
    ans[centroid] = rank;
    deleted[centroid] = true;

    // 4. 对重心的每一个邻居，如果它还没被处理，
    //    就以它为入口，对它所在的子连通块进行下一轮分解
    for (int v : adj[centroid]) {
        if (!deleted[v]) {
            decompose(v, rank + 1); // 军衔升一级（也就是字母往后一个）
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 从任意节点开始（比如 1），用最高的军衔 'A' 开始分解
    decompose(1, 'A');

    // 输出最终结果
    for (int i = 1; i <= n; ++i) {
        std::cout << ans[i] << (i == n ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

代码的逻辑和我们刚才分析的完全一样，是不是很清晰呢，喵？

---

知识点介绍：树的重心分解

最后，让本喵来给指挥官大人详细讲讲“树的重心分解”这个酷炫的算法吧！

什么是树的重心？

树的重心，也叫质心，是树中的一个特殊节点。当你把这个节点和与它相连的边都从树上移除后，剩下的森林（由若干个小树组成）中，最大的那棵树的节点数会尽可能小。

更精确的定义是：对于节点 u，令 max_subtree_size(u) 为移除 u 后产生的最大子树的节点数。重心就是那个使得 max_subtree_size(u) 最小的节点 u。

一个重要的性质是，这个最小的 max_subtree_size(u) 不会超过 floor(n/2)，其中 n 是原树的总节点数。这保证了分治的效率！

一棵树可能有一个或两个重心。如果有两个，它们一定是相邻的。

如何找到树的重心？

找重心的过程通常分两步：

1. 第一次 DFS: 从任意节点出发，计算出以每个节点为根的子树大小 sz[u]。
2. 第二次 DFS: 再次从根节点出发，对于当前节点 u，检查它的每一个子节点 v 的 sz[v]，以及它“上方”部分的大小 total_size - sz[u]。如果这些值中的最大值是所有节点中最小的，那么 u 就是重心。

代码中的 find_centroid 函数用了一种更巧妙的方法：它从一个点出发，不断往“重”的子树方向移动，直到当前节点的所有子树大小都不超过总大小的一半，那么这个节点就是重心。

什么是重心分解？

重心分解是一种处理树上路径问题的强大分治算法。它的核心思想是：

1. Divide (分解): 找到当前树的重心 c。
2. Conquer (解决):
   • 处理所有经过重心 c 的路径。在本题中，就是给 c 分配一个高级军衔，这个操作本身就“处理”了未来子问题之间的路径关系。
   • 移除 c，树会分裂成多个子树。
3. Combine (合并):
   • 对每个子树递归地进行重心分解。
   • 因为子树之间的问题已经被 c 解决了，所以子问题是独立的。

这个过程会形成一棵“重心树”，树的根是原树的重心，它的孩子是各个子树的重心，以此类推。由于每次分解，问题规模都至少减半，所以这棵重心树的深度是 O(log n) 的。这使得许多原本需要在树上进行 O(n^2) 暴力枚举路径的问题，可以用 O(n log n) 或 O(n log^2 n) 的时间复杂度解决。

好啦，指挥官大人，关于这个问题的一切就介绍到这里啦！希望本喵的讲解对您有帮助，喵~ 如果还有其他问题，随时可以再来找我哦！