算法标签

• 二分答案 (Binary Search)
• 贪心算法 (Greedy)
• 深度优先搜索 (DFS)
• 树形动态规划 (Tree DP)
• 换根DP (Rerooting DP)

题目解析

问题描述

给定一棵 $n$ 个节点的树和一个整数 $k$，我们需要为每个可能的根节点 $s$（首都）计算：通过添加不超过 $k$ 条有向边后，从 $s$ 到所有节点的最大距离的最小值。

关键点：

• 选择根 $s$ 后，树边自然变为从父节点指向子节点的有向边
• 可以添加最多 $k$ 条任意端点的有向边
• 目标是最小化从 $s$ 出发到所有节点的最远距离

核心思路

1. 二分答案框架

对于每个根节点 $s$，使用二分答案确定最小可达性 $D$：

• 下界：$0$（所有节点直接与根相连）
• 上界：$n-1$（树的直径）
• 检查是否存在添加 $\leq k$ 条边的方案，使得所有节点到 $s$ 的距离 $\leq D$

2. 贪心检查算法

对于给定的 $D$，使用 DFS 进行贪心检查：

def check(s, D):
    edges_needed = 0
    
    def dfs(u, parent):
        max_depth = 0
        for v in graph[u]:
            if v == parent: continue
            depth = dfs(v, u) + 1
            # 如果子树深度超过D且u不是根，需要加边
            if depth > D and u != s:
                edges_needed += 1
                return -1  # 加边后深度重置
            max_depth = max(max_depth, depth)
        return max_depth
    
    final_depth = dfs(s, -1)
    # 处理根节点的特殊情况
    if final_depth > D:
        edges_needed += 1
    
    return edges_needed <= k

贪心策略：当发现某个节点的子树最大深度等于 $D$ 时，在该节点处添加一条指向根的边，这样可以最大程度减少深度。

3. 不同情况的时间复杂度优化

• t=0（只求根节点1的答案）：直接二分，复杂度 $O(n \log n)$
• t=1（求所有节点的答案）：利用条件 $n \cdot k \leq 2 \times 10^5$，可以：
  • 对每个根进行二分：$O(n^2 \log n)$ 不可行
  • 使用换根DP：维护每个根下的深度信息，避免重复计算

算法正确性证明

贪心策略的最优性：

1. 在深度刚好为 $D$ 的节点处加边是最优的，因为可以覆盖整个子树
2. 每条边最多可以减少一个"深度违规"的子树
3. 从叶子向根处理可以确保尽早发现需要加边的位置

二分答案的单调性：

• 如果 $D$ 可行，那么所有 $D' > D$ 也可行
• 如果 $D$ 不可行，那么所有 $D' < D$ 也不可行

样例分析

样例1

输入：5 2 1
树结构：
    1
   / \
  2   3
 / \
4   5

计算过程：

• 根节点1：深度数组 [0,1,1,2,2]

  • $D=1$：深度>1的节点4,5需要覆盖，在节点2处加边（1条边≤2）✓
  • 答案=1

• 根节点3：深度数组 [1,2,0,3,3]

  • $D=1$：需要覆盖的节点太多（k不够）
  • $D=2$：深度>2的节点4,5需要覆盖，在节点2处加边（1条边）✓
  • 答案=2

输出：1 1 2 2 2

复杂度分析

• 时间复杂度：
  • t=0: $O(n \log n)$
  • t=1: $O(nk \log n)$ 或使用换根DP优化到 $O(n \log n)$
• 空间复杂度：$O(n)$

代码实现（C++）

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

int n, k, t;
vector<vector<int>> g;
int edges_needed;

int dfs(int u, int p, int D, int root) {
    int maxd = 0;
    for (int v : g[u]) {
        if (v == p) continue;
        int d = dfs(v, u, D, root) + 1;
        if (d > D && u != root) {
            edges_needed++;
            return -1;
        }
        maxd = max(maxd, d);
    }
    return maxd;
}

bool check(int root, int D) {
    edges_needed = 0;
    int d = dfs(root, -1, D, root);
    if (d > D) edges_needed++;
    return edges_needed <= k;
}

int solve_for_root(int root) {
    int l = 0, r = n, ans = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(root, mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

int main() {
    cin >> n >> k >> t;
    g.resize(n);
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    
    if (t == 0) {
        cout << solve_for_root(0) << endl;
    } else {
        vector<int> res(n);
        // 对于小数据直接计算，大数据需要换根DP优化
        for (int i = 0; i < n; i++) {
            res[i] = solve_for_root(i);
        }
        for (int i = 0; i < n; i++) {
            cout << res[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

优化技巧

1. 记忆化搜索：对于t=1的情况，可以缓存子树信息
2. 剪枝：当需要的边数已经超过k时立即返回
3. 迭代DFS：避免递归深度限制
4. 批量处理：对多个根节点同时进行二分搜索