[XR-3] 核心城市

形式化题目

给定一棵 $n$ 个节点的树，选一个恰好 $k$ 个节点的连通子集称为"核心"。定义其余节点到核心的距离为它到核心中最近节点的距离，称这些距离的最大值为拥堵度。求拥堵度的最小值。

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 08:02
 * update_at: 2026-08-13 08:02
 */
// brute.cpp：小数据暴力解，使用 01 序列递归枚举每个城市是否为核心城市。
// choose[i] = 1 表示第 i 个城市是核心城市；枚举完整序列后检查连通性并统计答案。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

int n, k;
vector<int> g[MAXN]; // 邻接表存树
int choose[MAXN];    // choose[i]：第 i 个城市是否被选为核心城市
int vis[MAXN];       // 连通性检查与 BFS 共用标记
int best = 1e9;

// 检查当前核心集合是否连通（只经过核心城市能否互相到达）。
bool check_connected() {
    int start = -1;
    for (int i = 1; i <= n; i++) {
        if (choose[i]) {
            start = i;
            break;
        }
    }
    if (start == -1)
        return false;
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    queue<int> q;
    vis[start] = 1;
    q.push(start);
    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cnt++;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (choose[v] && !vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    return cnt == k;
}

// 计算非核心城市 start 到最近核心城市的距离。
int dist_to_core(int start) {
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    queue<pair<int, int> > q; // 队列元素：(节点, 距离)
    vis[start] = 1;
    q.push(make_pair(start, 0));
    while (!q.empty()) {
        int u = q.front().first;
        int d = q.front().second;
        q.pop();
        if (choose[u])
            return d;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (!vis[v]) {
                vis[v] = 1;
                q.push(make_pair(v, d + 1));
            }
        }
    }
    return -1; // 不会到达
}

// 生成完整 01 序列后在叶子节点统一检查、统计。
void dfs(int dep, int cnt) {
    if (dep == n + 1) {
        if (cnt != k || !check_connected())
            return;
        int cur = 0;
        for (int i = 1; i <= n; i++) {
            if (!choose[i])
                cur = max(cur, dist_to_core(i));
        }
        if (cur < best)
            best = cur;
        return;
    }
    // 这一层决定第 dep 个城市选不选。
    choose[dep] = 0;
    dfs(dep + 1, cnt);
    choose[dep] = 1;
    dfs(dep + 1, cnt + 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);
    cout << best << '\n';
    return 0;
}

brute.cpp 用 01 序列枚举每个城市是否进入核心，到叶子节点再统一检查核心个数、连通性并 BFS 计算最远距离。 $2^n$ 种方案，只适合小数据。

关键观察是剥叶分层：把树理解成由外到内的同心层——叶子是第一层，剥掉叶子后新叶子是第二层，依此类推。每一轮剥掉的叶子构成一层，向内走一步就进入内层：

text

1
2
3
4第一轮剥掉：所有叶子（层号 1）
第二轮剥掉：新产生的叶子（层号 2）
……
第 t 轮剥掉：层号 t

剥叶过程保证"层号不小于某个值的节点"始终连通。于是最优核心就是层号最大的 $k$ 个节点（它们构成连通块），而拥堵度等于剩下节点中最大的层号——即层号降序排列后的第 $k+1$ 大。

以样例为例，剥叶分层如下：

节点	1	2	3	4	5	6
层号	2	3	1	1	2	1

$k = 3$ ：选层号最大的 $3$ 个节点 $2, 1, 5$ 为核心，第 $4$ 大层号是 $1$ ，答案为 $1$ ，与样例一致。观察"层号"列：非核心节点 $3, 4, 6$ 的层号都是 1，它们到核心集合的距离恰好也是 1。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-13 08:02
 * update_at: 2026-08-13 08:02
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, k;
vector<int> g[MAXN]; // 邻接表存树
int degree[MAXN];    // 当前剩余度数（剥叶过程中动态更新）
int layer[MAXN];     // layer[i]：节点 i 在第几轮被剥掉（叶子为第 1 轮）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        degree[u]++;
        degree[v]++;
    }

    // 拓扑剥叶：每一轮把所有当前叶子（剩余度数 <= 1）标记层数并删除。
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] <= 1) {
            layer[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (degree[v] > 1) {
                degree[v]--;
                if (degree[v] == 1) {
                    layer[v] = layer[u] + 1;
                    q.push(v);
                }
            }
        }
    }

    // 选 layer 最大的 k 个点作核心（剥叶剩余部分连通），
    // 第 k+1 大的 layer 值就是非核心点到核心的最大距离。
    sort(layer + 1, layer + n + 1, greater<int>());
    cout << layer[k + 1] << '\n';
    return 0;
}

复杂度

时间：剥叶 $O(n)$ + 排序 $O(n \log n)$ 。
空间：邻接表与层号数组， $O(n)$ 。

总结

"选 $k$ 个连通节点使最大距离最小"的通用套路是剥叶分层：核心一定是最内层的连通块，层号本身就是距离的度量。剥叶用拓扑排序的队列写法实现，一轮 $O(n)$ ，是最常考的树结构建模。

图示解析

这张 ASCII 图展示整道题的解题路线：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17朴素模拟（brute.cpp）
  01 序列枚举每个城市是否核心 + 连通检查 + BFS 最远距离     O(2^n)
        |
        | 瓶颈：组合数爆炸，必须找到核心集合的结构特征
        v
关键观察（剥叶分层）
  叶子 = 第 1 层；剥掉后再剥新叶子 = 第 2 层……
  层号不小于某值的节点始终连通
  核心 = 层号最大的 k 个节点（连通），非核心最大距离 = 第 k+1 大层号
        |
        v
拓扑剥叶（main.cpp）
  队列维护当前叶子，动态更新度数
  层号 = 被剥轮次；降序排序后取第 k+1 大
        |
        v
复杂度 O(n log n)，空间 O(n)

图中三条主线对应"暴力慢在哪"“剥叶为什么能同时给出连通核心与距离度量”“队列写法如何一遍剥完”。核心是把"选连通子集"转成"按层号取前 k 大"——连通性由剥叶过程免费保证。

目录

形式化题目

思路

代码

复杂度

总结

图示解析