【XR-3】核心城市

GitHub跳转原题关系图返回列表

叶层剥离得到每个城市的离叶层数，直接选出最小可行核心半径。

OJ: luogu

题目 ID: P5536

难度:普及+/提高-

标签:树拓扑剥离贪心python

日期: 2026-07-17 02:00

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

选择恰好 k 个互相连通的核心城市，使非核心城市到核心的最大距离最小。

思路

不断删除当前叶子并记录删除层数。删除 r 层后剩余节点仍连通，且所有被删节点到剩余部分距离不超过 r；反过来，任何半径为 r 的连通核心都必须包含未被前 r 层剥离的节点。因此将层数降序排列，第 k+1 大层数就是最小答案。

Python 知识

  • deque 实现叶子队列，度数减到 1 时入队。
  • sorted(..., reverse=True)[k] 直接取第 k+1 大层数。
  • 每个节点只入队一次，代码比二分判定更短。

代码

python
import sys
from collections import deque


input = sys.stdin.buffer.readline
n, core_count = map(int, input().split())
graph = [[] for _ in range(n + 1)]
degree = [0] * (n + 1)
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    degree[u] += 1
    degree[v] += 1

layer = [0] * (n + 1)
queue = deque()
for node in range(1, n + 1):
    if degree[node] <= 1:
        layer[node] = 1
        queue.append(node)
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if degree[neighbor] > 1:
            degree[neighbor] -= 1
            if degree[neighbor] == 1:
                layer[neighbor] = layer[node] + 1
                queue.append(neighbor)
print(sorted(layer[1:], reverse=True)[core_count])

原有 C++ 版本仍保留：

cpp
/**
 * 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-07-17 01:04
 * update_at: 2026-07-17 01:04
 */
#include <bits/stdc++.h>
using namespace std;

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

    return 0;
}

复杂度

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

总结

连通核心的半径可以从树的外层向内剥离来理解。