[NOIP 2015 提高组] 运输计划

P3128 Max Flow P (你已经搞定，点差分基础)
CF191C Fools and Roads (边差分基础，学会映射边 ID)
P6869 Putovanje (边差分进阶，学会统计覆盖次数后做决策，这题做完就可以直接去杀 P2680 了)
(可选) P3258 松鼠的新家 (磨练细节处理能力)
P2680 运输计划 (最终 BOSS：边差分 + 二分答案)

题目解析

错误想法

求出每条路径的时间(长度),然后减去路径上的最长边,答案是这些值的最小值

1. “全局唯一” vs “各自为政”

题目限制：你只能把全图中的某一条边变成虫洞（权值为 0）。这意味着，这条被选中的边，必须对所有需要缩短的路径生效。

你的思路：

“每条路径减去该路径上的最长边”。

这隐含了一个假设：你可以为每一条路径单独指定一个虫洞。

路径 A 可以删掉它自己的最长边 $E_a$ 。
路径 B 可以删掉它自己的最长边 $E_b$ 。

现实情况：

如果 $E_a$ 和 $E_b$ 不是同一条边，你不可能同时删掉它们。你只能二选一（或者选一条它们共用的其他边）。如果你删了 $E_a$ ，路径 B 的长度可能完全没变，导致最终的最大值依然很大。

2. “木桶效应”：我们要的是 Min-Max

题目目标：所有运输计划同时结束，取决于最慢的那一个。我们要让这个最慢的时间尽可能短（Minimize the Maximum）。

你的思路：

“答案是这些值的最小值”。

这意味着你求的是：“在理想情况下，跑得最快的那条路径能有多快”。

现实情况：

最快的路径跑得再快也没用，系统完成时间取决于最慢的那条路径（瓶颈）。你需要关心的是那些“超长路径”能不能被同一条边切断并缩短。

暴力想法

枚举每条边为0,然后dfs找出所有路路径的长度,求出最大小值,

TLE

二分

求最大时间最小,显然是二分答案啊. 所以从二分开始考虑

$T_i$ 表示路径 i 的总时间

枚举一个答案时间 $T_a$ ,把 $T_i$ 分成两类

$T_i <= T_a$ 合法,不用管
$T_i > T_a$ 不合法,超标,

问题变成: **怎么能让(或者是否可以) 超标的路合法 ? **, 可以想到,

一定是删除(置0)所有超标路的公共边中最大的那条边, 不删除公共边,没有意义
找到公共边: 树上差分

思考二分性:

如果 $T_a$ 成立: $T_a$ 条件下 $\forall T_i \leqslatn T_a$ , 则%T_a + 1% 成立

我们显然要要找到第一个成立的 $T_a$

解析2

核心目标：

在树上选定一条边，将其权值变为 0，使得所有给定路径中，最长的那条路径的长度最小。

思维导图：

“最大值最小” $\rightarrow$ 二分答案
- 这类问题通常具备单调性：如果能在 $T$ 时间内完成，那么在 $T+1$ 时间肯定也能完成。
- 我们可以二分一个时间限制 $T$ 。
如何检查时间 $T$ 是否可行？ (check(T))
- 找出所有长度 $> T$ 的路径（我们称之为“超标路径”）。
- 如果没有超标路径，说明 $T$ 可行，直接返回 True。
- 如果有，我们需要找到一条边，满足以下两个条件：
  1. 这条边被所有“超标路径”共同经过（只有切断所有超标路径的公用边，才能把它们都缩短）。
  2. 最长的那条超标路径减去这条边的权值后，长度 $\le T$ 。
- 如果能找到这样的边，说明 $T$ 可行。
如何快速找到被所有超标路径经过的边？ $\rightarrow$ 树上边差分
- 假设有 $cnt$ 条超标路径。
- 对于每条超标路径 $(u, v)$ ，我们在树上做差分：diff[u]++, diff[v]++, diff[lca(u,v)] -= 2。
- 做完后，从下往上统计前缀和。如果某个点 $u$ 的权值 sum[u] == cnt，说明 $u$ 到其父亲的这条边被所有 $cnt$ 条路径经过。

算法流程：

预处理：计算 LCA，计算每个点到根的距离 dist，把所有路径的长度、LCA 都算好存起来（避免二分时重复算）。
二分答案：范围 $[0, \text{最长路径长度}]$ 。
Check 函数：利用树上差分判断。

2. 代码实现

基于你的模板，我做了以下适配：

内存调整： $N=300,000$ ，数组大小设为 300005。
LCA 增强：在 DFS 过程中顺便计算 dist（节点到根距离）和 val（节点到父亲的边权）。
预处理：因为二分 check 会调用很多次，所以先把 $m$ 个询问的 LCA 和原始长度算好存数组里。

复杂度分析

时间复杂度：
- 预处理 LCA: $O(N \log N)$
- 预处理查询: $O(M \log N)$
- 二分 Check: $O(\log(\text{MaxLen}) \times (N + M))$ 。其中 $N$ 是 DFS 的开销， $M$ 是遍历查询的开销。
- 总时间: $O(M \log N + (N+M) \log (\text{Len})) \approx 10^7$ 级别，完全可以通过 1s 的时限。
空间复杂度：
- $O(N \times 20)$ 用于倍增数组，约为 24MB，加上其他数组，远小于 128MB。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-03
 */
#include <bits/stdc++.h>
using namespace std;

// P2680 N, M <= 300,000
const int maxn = 300005; 
const int maxe = 600005; // 双向边

int n, m;
int diff[maxn];   // 差分数组
int val[maxn];    // val[u] 表示 u 到 fa[u] 的边权
int dist[maxn];   // dist[u] 表示 u 到 root 的距离
int max_edge_on_limit_path; // 辅助变量

// 存储查询，避免二分时重复计算 LCA
struct Query {
    int u, v, lca, len;
} q[maxn];

// === 链式前向星 ===
struct linkList {
    typedef struct {int u,v,w,next;} edge;
    edge e[maxe];
    int h[maxn], edge_cnt;
    
    linkList(){ reset(); }
    void reset() { edge_cnt=0; memset(h,-1,sizeof(h)); }
    
    void add2(int u, int v, int w) {
        e[edge_cnt] = {u, v, w, h[u]}; h[u] = edge_cnt++;
        e[edge_cnt] = {v, u, w, h[v]}; h[v] = edge_cnt++;
    }
    
    edge& operator[](int i){ return e[i]; }

    // Iterator 语法糖 (为了节省篇幅，这里简化为只用 adj)
#ifdef __cpp_range_based_for
    struct AdjIterator {
        int i; linkList* p;
        AdjIterator(linkList* p, int i) : p(p), i(i) {}
        AdjIterator& operator++() { i = p->e[i].next; return *this; }
        bool operator!=(const AdjIterator& oth) { return i != oth.i; }
        // 返回 pair<int, int> : {v, w}
        pair<int, int> operator*() { return {p->e[i].v, p->e[i].w}; }
    };
    struct BaseRange {
        int start; linkList* p;
        BaseRange(linkList* p, int start) : p(p), start(start) {}
        AdjIterator begin() { return AdjIterator(p, p->h[start]); }
        AdjIterator end()   { return AdjIterator(p, -1); }
    };
    BaseRange adj(int u) { return BaseRange(this, u); }
#endif
} e;

// === LCA 模板 ===
const int MAXLOG = 20;   
struct LCA {
    int f[maxn][MAXLOG + 1];
    int d[maxn];

    void init(int n, int root){
        dfs(root, 0, 1, 0); 
        // 黑洞优化
        for (int j = 1; j <= MAXLOG; ++j) {
            for (int i = 1; i <= n; ++i) {
                f[i][j] = f[ f[i][j-1] ][ j-1 ];
            }
        }
    }

    // DFS: 顺便处理 dist 和 val
    void dfs(int u, int fa, int depth, int w_from_fa) {
        d[u] = depth;
        f[u][0] = fa; 
        val[u] = w_from_fa; // 记录边权
        
        for (auto [v, w] : e.adj(u)) { // 使用修改后的语法糖，拿到 w
            if (v != fa) {
                dist[v] = dist[u] + w;
                dfs(v, u, depth + 1, w);
            }
        }
    }

    int ask(int u, int v) {
        if (d[u] < d[v]) swap(u, v);
        for (int i = MAXLOG; i >= 0; --i) {
            if (d[u] - (1 << i) >= d[v]) u = f[u][i];
        }
        if (u == v) return u;
        for (int i = MAXLOG; i >= 0; --i) {
            if (f[u][i] != f[v][i]) {
                u = f[u][i];
                v = f[v][i];
            }
        }
        return f[u][0];
    }
} lca;

// === 核心 Check 函数 ===
// 检查是否能在 limit 时间内完成
// 统计 diff 的 DFS
// u 当前点 , fa 父节点
// cnt 不达标的边的数量
// max_path_len 最长的边的值
// limit 边长的上线
bool dfs_check(int u, int fa, int cnt, int max_path_len, int limit) {
    bool found = false;
    for(auto [v, w] : e.adj(u)) {
        if(v == fa) continue;
        if(dfs_check(v, u, cnt, max_path_len, limit)) found = true; // 只要子树找到了，就标记
        diff[u] += diff[v]; // 累加差分
    }
    
    // 如果已经找到了可行解，不需要继续判断当前点，但需要继续回溯累加diff
    if (found) return true;

    // 核心判断：
    // 1. diff[u] == cnt : 说明这条边 (u, fa) 被所有超标路径覆盖
    // 2. max_path_len - val[u] <= limit : 减去这条边后，最长的那条路径满足限制
    if (diff[u] == cnt && max_path_len - val[u] <= limit) {
        return true;
    }
    return false;
}

bool check(int limit) {
    memset(diff, 0, sizeof(int) * (n + 1));
    int cnt = 0;           // 超标路径数量
    int max_len = 0;       // 超标路径中的最大长度

    // 1. 找出所有超标路径，并进行差分
    for(int i = 1; i <= m; ++i) {
        if(q[i].len > limit) {
            cnt++;
            max_len = max(max_len, q[i].len);
            // 边差分：u++, v++, lca -= 2
            diff[q[i].u]++;
            diff[q[i].v]++;
            diff[q[i].lca] -= 2;
        }
    }

    // 如果没有超标路径，说明 limit 是可行的（不需要删边）
    if(cnt == 0) return true;

    // 2. DFS 统计差分并寻找符合条件的边
    // 从根节点 1 开始
    return dfs_check(1, 0, cnt, max_len, limit);
}

void init(){
    cin >> n >> m;
    for(int i = 1; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        e.add2(u, v, w);
    }
    
    lca.init(n, 1);

    // 预处理所有查询
    for(int i = 1; i <= m; ++i) {
        cin >> q[i].u >> q[i].v;
        q[i].lca = lca.ask(q[i].u, q[i].v);

        //树上唯一路径的 长度
        q[i].len = dist[q[i].u] + dist[q[i].v] - 2 * dist[q[i].lca];
    }
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    
    init();

    // 二分答案
    // 左边界 0，右边界为最长路径（或者所有边权和，这里取个大数就行，最长路径肯定<=边权和）
    int l = 0, r = 300000 * 1000; // 最坏情况
    // 优化右边界：取所有计划中的最大长度
    int max_q_len = 0;
    for(int i=1;i<=m;++i) max_q_len = max(max_q_len, q[i].len);
    r = max_q_len;

    int ans = max_q_len;

    while(l < r) {
        int mid = (l + r) >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid; // 尝试更小的时间
        } else {
            l = mid + 1; // 必须更长时间
        }
    }

    cout << ans << endl;
    
    return 0;
}