题目理解

我们有一个包含 $n$ 个交叉口的树形道路网络，需要选择最多 $k$ 个终点站（度数为1的节点），使得所有节点到最近地铁站的最大距离（烦躁系数）最小。

关键约束：

• 终点站数量 $s \leq k$ 且 $s \geq 2$
• 终点站必须是叶子节点（度数为1）
• 目标是先最小化最大烦躁系数 $r$，再最小化终点站数量 $s$

问题分析

这是一个树上的设施选址问题，结合了最小覆盖半径和设施数量限制。

核心思路

1. 二分答案：对于候选的烦躁系数 $r$，检查是否存在选择不超过 $k$ 个叶子节点作为终点站，使得所有节点到最近站点的距离不超过 $r$

2. 贪心选择：在树上从叶子向根进行贪心覆盖

算法步骤

步骤1：二分查找最小烦躁系数

def solve():
    low, high = 0, n  # r的范围
    while low <= high:
        mid = (low + high) // 2
        if check(mid):  # 检查r=mid是否可行
            ans_r = mid
            high = mid - 1
        else:
            low = mid + 1

步骤2：检查特定r的可行性

使用树形DP或贪心算法检查：

def check(r):
    # 返回是否可以用不超过k个叶子节点覆盖整棵树，且最大距离≤r
    # 同时记录最小的s
    cnt, covered = greedy_cover(r)
    return cnt <= k and covered

步骤3：贪心覆盖算法

从叶子节点开始向上贪心：

1. DFS遍历：后序遍历树，计算每个节点到最近未覆盖叶子的距离
2. 覆盖策略：
   • 当一个节点到最远未覆盖叶子的距离等于 $r$ 时，选择该节点作为覆盖点
   • 或者当必须选择叶子时，选择深度合适的叶子
3. 验证约束：确保选择的都是叶子节点且数量不超过 $k$

步骤4：构造解

找到最小的 $r$ 后，重新运行覆盖算法来记录具体的站点选择。

关键技巧

1. 树的性质利用

• 树的直径：最大烦躁系数至少是直径的一半
• 叶子节点特性：只有叶子可以作为终点站

2. 贪心证明

贪心选择的正确性基于：

• 如果不在当前位置设站，某些节点将无法被覆盖
• 选择当前最优的叶子不会使后续解变差

3. 时间复杂度优化

• 二分查找：$O(\log n)$
• 每次检查：$O(n)$
• 总复杂度：$O(n \log n)$，适合 $n \leq 3 \times 10^6$

算法实现细节

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e6 + 5;

vector<int> graph[MAXN];
int n, k;
int depth[MAXN], max_depth[MAXN];
bool is_leaf[MAXN];
vector<int> stations;

// 计算深度和标记叶子
void dfs_depth(int u, int parent) {
    is_leaf[u] = (graph[u].size() == 1);
    max_depth[u] = depth[u];
    for (int v : graph[u]) {
        if (v == parent) continue;
        depth[v] = depth[u] + 1;
        dfs_depth(v, u);
        max_depth[u] = max(max_depth[u], max_depth[v]);
    }
}

// 检查r是否可行，并返回最小站点数
pair<bool, int> check_r(int r) {
    // 实现贪心覆盖算法
    // 返回(是否可行, 最小站点数)
}

// 构造解
void build_solution(int r, int s) {
    // 根据找到的r和s构造具体的站点选择
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // 找到根节点（非叶子）
    int root = 1;
    while (graph[root].size() == 1) root++;
    
    depth[root] = 0;
    dfs_depth(root, -1);
    
    // 二分查找
    int left = 0, right = n, best_r = n, best_s = k;
    while (left <= right) {
        int mid = (left + right) / 2;
        auto [possible, min_stations] = check_r(mid);
        if (possible && min_stations <= k) {
            best_r = mid;
            best_s = min_stations;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    build_solution(best_r, best_s);
    cout << best_r << " " << best_s << endl;
    // 输出具体站点
    for (int station : stations) {
        cout << station << " ";
    }
    cout << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 二分查找：$O(\log n)$
  • 每次检查：$O(n)$
• 空间复杂度：$O(n)$

算法标签

• 树结构 (Tree Structure)
• 贪心算法 (Greedy Algorithm)
• 二分查找 (Binary Search)
• 深度优先搜索 (DFS)
• 设施选址问题 (Facility Location Problem)

总结

本题通过二分答案确定最小烦躁系数，结合树上的贪心覆盖算法来选择最优的终点站位置。关键在于利用树的结构特性和贪心选择的正确性证明，在满足约束条件的同时优化目标函数。

对于大数据范围 ($n \leq 3 \times 10^6$)，算法具有良好的可扩展性，能够高效解决问题。