题解归档 - cf321C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf321C
• 本地来源：problems/cf321C/idea.md
• 题目链接：https://codeforces.com/contest/321/problem/C
• 原始标题：CF321C — Ciel the Commander

思路

CF321C — Ciel the Commander

Catalog：Trees / Centroid → lib/图论(点分治).cpp

题意

给一棵 n 个点的树，给每个点分配一个军衔 A..Z（A 最高）。要求：任意两个不同城市若军衔相同，则它们简单路径上存在军衔更高（字母更小）的城市。

若可行输出 n 个字母，否则 Impossible!。

做法：点分治

关键观察：若当前连通块内选重心 c 赋当前层字符 ch，则：

• c 是整块中「分隔者」，任意跨子树的点对路径必经过 c；
• 每个子连通块递归用 ch+1 分配，深度不超过 26 即全局可行。

n≤10^5 时点分治层数为 O(log n) ≤ 18 < 26，故除递归层数意外溢出外总有解；实现中 dep≥26 时输出 Impossible!。

实现要点

1. dfs_sz：在未被删除点集上算子树大小；
2. dfs_cen：找重心（最大子块 ≤ tot/2）；
3. dfs_cd(u, dep)：标 ans[cen]='A'+dep，删重心，对每个子连通块 dfs_cd(child, dep+1)。

复杂度

时间 O(n log n)，空间 O(n)。

验证

• 样例 1：A B B B（星形，中心 A，叶子 B，路径经 A）
• 链 n=10：合法方案不唯一，点分治输出与官方样例不同但均合法

代码

来源：problems/cf321C/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:27
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005;
vector<ll>ss[maxn];
ll sz[maxn],pd[maxn];
char ans[maxn];
bool imp;
void dfs_sz(ll x,ll fa){
    ll i,dq;
    sz[x]=1;
    for(i=0;i<(ll)ss[x].size();i++){
        dq=ss[x][i];
        if(dq==fa or pd[dq]) continue;
        dfs_sz(dq,x);
        sz[x]+=sz[dq];
    }
}
ll dfs_cen(ll x,ll fa,ll tot){
    ll i,dq;
    for(i=0;i<(ll)ss[x].size();i++){
        dq=ss[x][i];
        if(dq==fa or pd[dq]) continue;
        if(sz[dq]>tot/2) return dfs_cen(dq,x,tot);
    }
    return x;
}
void dfs_cd(ll x,ll dep){
    if(dep>=26){
        imp=1;
        return;
    }
    ll i,dq,tot,cen;
    dfs_sz(x,-1);
    tot=sz[x];
    cen=dfs_cen(x,-1,tot);
    ans[cen]='A'+dep;
    pd[cen]=1;
    for(i=0;i<(ll)ss[cen].size();i++){
        dq=ss[cen][i];
        if(pd[dq]) continue;
        dfs_cd(dq,dep+1);
    }
}
int main(){
    ll n,i,x,y;
    cin>>n;
    for(i=1;i<n;i++){
        cin>>x>>y;
        ss[x].push_back(y);
        ss[y].push_back(x);
    }
    imp=0;
    dfs_cd(1,0);
    if(imp){
        cout<<"Impossible!\n";
        return 0;
    }
    for(i=1;i<=n;i++){
        if(i>1) cout<<" ";
        cout<<ans[i];
    }
    cout<<"\n";
    return 0;
}