题解：CF321C Ciel the Commander

CF321C

题意

给定一颗包含

n

个结点的树，需要给每个结点编号 A ~ Z，其中 A 是最高级，Z 是最低级。

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

思路

我们会发现这个等级只有

26

种，大概就是

\log n

种。

因此，我们可以考虑依靠重心将整棵树分为

\log n

层，每一条经过重心的路径都会有重心满足条件。

CPP

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);
}

题解：CF321C Ciel the Commander

文章操作

CF321C

题意

思路

相关推荐

评论

题解：CF321C Ciel the Commander