题解：CF321C Ciel the Commander

Yan719 · 2025-11-25 15:05:47 · 题解

CF321C

题意

给定一颗包含 n 个结点的树，需要给每个结点编号 A ~ Z，其中 A 是最高级，Z 是最低级。

要求满足每两个点之间的路径上都有一个等级比这两个点高的点存在。

思路

我们会发现这个等级只有 26 种，大概就是 \log n 种。

因此，我们可以考虑依靠重心将整棵树分为 \log n 层，每一条经过重心的路径都会有重心满足条件。

void DFS(int u, int fa) {
    sz[u] = 1, mmax[u] = 0;
    dot.push_back(u);
    for (int v : g[u]) {
        if (fa != v && !vis[v]) {
            DFS(v, u), sz[u] += sz[v];
            mmax[u] = max(mmax[u], sz[v]);
        }
    }
}

void Solve(int u, char c) {
    dot.clear(), DFS(u, 0);
    int h = 0;
    for (int x : dot) {
        if (max(mmax[x], sz[u] - sz[x]) <= sz[u] / 2) {
            h = x; break;
        }
    }
    vis[h] = 1, ans[h] = c;
    for (int v : g[h]) if (!vis[v]) Solve(v, c + 1);
}