赛道修建详细题解

问题描述

C城有$n$个路口和$n-1$条道路，形成一棵树结构。需要修建$m$条赛道，每条赛道是互不重叠的道路组成的路径，赛道长度为路径上道路长度之和。要求设计方案使$m$条赛道中最短的那条长度尽可能大，求这个最大可能值。

算法思路

本题采用二分答案+树形贪心的解法，核心步骤如下：

1. 二分答案：假设最短赛道的最大可能长度为$mid$，通过二分法在$[0, 10^9]$范围内寻找这个值。
2. 可行性检查：对每个候选$mid$，判断能否在树中修建至少$m$条长度≥$mid$的赛道。检查通过深搜实现，过程如下：
   • 递归处理每个节点的子树，收集子树中未被使用的路径长度（从子节点到当前节点的路径）。
   • 对收集的路径长度排序，优先选择能单独形成赛道（长度≥$mid$）的路径，再通过贪心配对剩余路径（两条路径之和≥$mid$），统计可形成的赛道数量。
   • 若总数量≥$m$，则$mid$可行，尝试更大值；否则不可行，尝试更小值。

代码解析

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;  // 最大节点数
int n, m, tot, l, r, mid, cnt, head[N], maxn[N], q[N], father[N];
bool vis[N];  // 标记路径是否被使用

// 边的结构体：存储邻接表
struct edge {
    int next, to, dis;
} e[N * 2];  // 双向边，开2倍空间

// 添加边
void add(int from, int to, int dis) {
    e[++tot].to = to;
    e[tot].dis = dis;
    e[tot].next = head[from];
    head[from] = tot;
}

// 并查集：用于快速查找未被使用的路径
int find(int x) {
    return x == father[x] ? x : father[x] = find(father[x]);
}

// 深搜检查：以x为根，fa为父节点，检查能否形成足够多长度≥len的赛道
void dfs(int x, int fa, int len) {
    int r = 0, l = 1;  // q数组的左右指针

    // 先递归处理所有子节点
    for (int i = head[x]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa)  // 避免访问父节点
            dfs(v, x, len);
    }

    // 收集子节点返回的最大路径长度（加上当前边的长度）
    for (int i = head[x]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa) {
            q[++r] = maxn[v] + e[i].dis;  // 子路径+当前边长度
            vis[r] = 0;  // 初始未使用
            father[r] = r;  // 并查集初始化
        }
    }

    int k = r;  // 记录总路径数
    sort(q + 1, q + 1 + r);  // 对路径长度排序

    // 第一步：处理能单独形成赛道的路径（长度≥len）
    for (; q[r] >= len; r--) {
        cnt++;  // 计数+1
        vis[r] = 1;  // 标记为已使用
    }

    // 第二步：贪心配对剩余路径，使两条路径之和≥len
    for (; l <= r; l++) {
        if (vis[l]) continue;  // 跳过已使用的

        // 寻找最小的p，使q[p] ≥ len - q[l]
        int p = lower_bound(q + l + 1, q + r + 1, len - q[l]) - q;
        p = find(p);  // 找到未被使用的p

        if (p <= r && p > l) {  // 找到有效配对
            cnt++;  // 计数+1
            vis[p] = vis[l] = 1;  // 标记为已使用
            // 并查集路径压缩，下次直接找下一个未使用的
            father[find(l)] = find(l + 1);
            father[find(p)] = find(p + 1);
        }
    }

    // 记录当前节点能向上提供的最长未使用路径
    for (int i = k; i >= 1; i--) {
        if (!vis[i]) {
            maxn[x] = q[i];
            break;
        }
    }
}

int main() {
    memset(head, -1, sizeof(head));  // 邻接表初始化
    scanf("%d%d", &n, &m);

    // 读入边并建图
    for (int i = 1, x, y, z; i < n; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);  // 双向边
    }

    // 二分答案：寻找最大的最小赛道长度
    l = 0;
    r = 1e9;  // 最大可能长度（道路长度≤1e4，最多5e4条，总和≤5e8，1e9足够）

    while (l <= r) {
        mid = (l + r) >> 1;  // 中间值
        memset(maxn, 0, sizeof(maxn));  // 重置每个节点的最大路径
        memset(vis, 0, sizeof(vis));  // 重置使用标记
        cnt = 0;  // 重置赛道计数
        dfs(1, 0, mid);  // 以1为根检查

        if (cnt >= m)  // 可行，尝试更大值
            l = mid + 1;
        else  // 不可行，尝试更小值
            r = mid - 1;
    }

    printf("%d", l - 1);  // 最终答案为l-1（最后一次可行的mid）
    return 0;
}

关键逻辑说明

1. 二分答案：通过二分法高效缩小最短赛道的最大可能长度。每次判断$mid$是否可行，将问题转化为Yes/No判定。

2. 树形处理：

   • 深搜递归处理每个节点的子树，自底向上收集路径信息。
   • 对每个节点的子路径排序，优先使用长路径单独成赛道，再配对短路径，最大化赛道数量。

3. 并查集优化：在配对路径时，用并查集快速找到未被使用的路径，避免重复配对，降低时间复杂度。

样例分析

样例1

• 输入：$n=7$，$m=1$，树结构如题目描述。
• 二分过程：最终$mid=31$时，可形成1条赛道（4-2-1-3-7，长度$9+10+5+7=31$），故答案为$31$。

样例2

• 输入：$n=9$，$m=3$，树结构如题目描述。
• 二分过程：$mid=15$时，可形成3条赛道（长度分别为15、16、17），满足条件；$mid=16$时无法形成3条，故答案为$15$。

复杂度分析

• 时间复杂度：二分次数为$O(\log L)$（$L=1e9$，约$30$次），每次深搜处理$n$个节点，每个节点的子路径排序复杂度为$O(k \log k)$（$k$为子节点数），总复杂度为$O(n \log n \log L)$，适合$n \le 5 \times 10^4$的规模。
• 空间复杂度：$O(n)$，用于存储树、路径数组及辅助数组。

算法标签

• 二分答案
• 树形DP
• 贪心算法
• 并查集
• 深度优先搜索（DFS）

数据范围

• 所有数据：$2 \le n \le 5 \times 10^4$，$1 \le m \le n-1$，$1 \le a_i, b_i \le n$，$1 \le l_i \le 10^4$。