题解：P2680 [NOIP 2015 提高组] 运输计划

0Io_oI0 · 2025-03-02 00:20:07 · 题解

~~感谢本题教会我无数卡常技巧 qwq~~

题目大意：

有一个 n 个结点，n-1 条边的树状图，有 m 次运输，每次运输从 u_i 运送到 v_i 的最短路径。现在可以将某个路径变成虫洞，来节省时间，求将某个路径变成虫洞后，每个任务所需要的最短时间。

思路

看完这道题目以后，我们的大致思路为：采用二分查找来确定最短时间。对于 mid，检查是否存在一条航道，将其改造成虫洞后，所有运输的最长时间不超过 mid。而在求路径长的时候我们需要用到 LCA。

大体的步骤如下：

使用 BFS 初始化节点的父节点、深度和距离。
使用倍增预处理 up 数组，用来计算 LCA。
计算计划的起点和终点的 LCA 和路径长。
进行二分查找，对于每个 mid，查看是否存在一条边，将其变为虫洞后，所有运输的最大时间不超过 mid。
使用差分标记长度超过 mid 的运输路径，检查是否存在满足条件的边。

如果还有疑问，可以看代码注释：

#include<bits/stdc++.h> 
#define I using 
#define AK namespace 
#define IOI std 
#define i_ak return 
#define ioi 0 
#define int long long // 使用long long类型 

I AK IOI; 

const int MAXN=3e5+5; // 最大节点数 
const int LOG=20;      // LCA倍增的层数 

int n,m; 
int parent[MAXN],depth[MAXN],w[MAXN]; // 父节点/深度/边权 
int up[LOG][MAXN];                    // LCA倍增数组 
int dist[MAXN];                       // 根节点到各点距离 
int nodes_order[MAXN];                // 按深度排序的节点序列 

// 邻接表结构体（模拟vector<pair>）
struct Edge{
    int to,t;         // 相邻节点和边权 
    int next;         // 下条边索引 
}edges[MAXN<<1];      // 双向边需要两倍空间 
int head[MAXN],edge_cnt; 

// 运输计划结构体 
struct Query{
    int u,v,lca; 
    int len;          // 原始路径长度 
}q[MAXN]; 

// 链式前向星加边 
void add_edge(int a,int b,int t){
    edges[++edge_cnt] = {b,t,head[a]};
    head[a] = edge_cnt;
}

// BFS预处理树结构 
void bfs(int root){
    queue<int> que; 
    que.push(root); 
    parent[root] = -1; 
    depth[root] = 0; 
    dist[root] = 0; 

    while(!que.empty()){
        int u=que.front(); que.pop(); 
        // 遍历邻接表 
        for(int i=head[u];i;i=edges[i].next){
            int v=edges[i].to, t=edges[i].t; 
            if(v == parent[u]) continue; 

            parent[v] = u; 
            depth[v] = depth[u]+1; 
            w[v] = t; 
            dist[v] = dist[u]+t; 
            que.push(v); 
        }
    }
}

// 预处理LCA的倍增数组 
void pre_lca(){
    for(int i=1;i<=n;++i) up[0][i] = (parent[i]==-1) ? i : parent[i]; 
    for(int k=1;k<LOG;++k)
        for(int i=1;i<=n;++i)
            up[k][i] = up[k-1][up[k-1][i]]; 
}

// 查询LCA 
int lca(int u,int v){
    // 先调整到同一深度 
    if(depth[u]<depth[v]) swap(u,v); 
    for(int k=LOG-1;k>=0;--k)
        if(depth[up[k][u]] >= depth[v]) 
            u = up[k][u]; 
    if(u == v) return u; 
    // 一起向上跳 
    for(int k=LOG-1;k>=0;--k)
        if(up[k][u] != up[k][v])
            u=up[k][u],v=up[k][v]; 
    return parent[u]; 
}

// 预处理所有查询的LCA和路径长度 
void pre_queries(){
    for(int i=0;i<m;++i){
        int u=q[i].u, v=q[i].v; 
        int l=lca(u,v); 
        q[i].lca = l; 
        q[i].len = dist[u] + dist[v] - 2*dist[l]; 
    }
}

// 检查mid是否可行 
bool check(int mid){
    int diff[MAXN]={0};       // 差分数组 
    int max_gap=0, cnt=0;     // 最大需要消减的差值/超限路径数 
    int S[MAXN],s_cnt=0;      // 存储超限的路径 

    // 筛选超限的运输计划 
    for(int i=0;i<m;++i){
        if(q[i].len > mid){
            S[s_cnt++] = i; 
            max_gap = max(max_gap, q[i].len - mid); 
        }
    }
    if(s_cnt == 0) return true; 

    // 树上差分操作 
    for(int i=0;i<s_cnt;++i){
        int u=q[S[i]].u, v=q[S[i]].v, l=q[S[i]].lca; 
        diff[u]++, diff[v]++, diff[l]-=2; 
    }
    // 自底向上传递差分值 
    for(int i=0;i<n;++i){
        int u=nodes_order[i]; 
        if(parent[u] == -1) continue; 
        diff[parent[u]] += diff[u]; 
    }
    // 检查是否存在公共边 
    for(int u=2;u<=n;++u) 
        if(diff[u]==s_cnt && w[u]>=max_gap) 
            return true; 
    return false; 
}

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

    cin>>n>>m; 
    // 读取边并建图 
    for(int i=0;i<n-1;++i){
        int a,b,t; cin>>a>>b>>t; 
        add_edge(a,b,t); add_edge(b,a,t); 
    }
    bfs(1); // 预处理树结构 

    // 按深度降序排序节点 
    for(int i=0;i<n;++i) nodes_order[i] = i+1; 
    sort(nodes_order,nodes_order+n,[&](int a,int b){
        return depth[a] > depth[b]; 
    }); 

    pre_lca(); // 预处理LCA 

    // 读取所有查询 
    for(int i=0;i<m;++i) cin>>q[i].u>>q[i].v; 
    pre_queries(); // 预处理查询数据 

    // 二分答案 
    int max_len=0; 
    for(int i=0;i<m;++i) max_len=max(max_len, q[i].len); 
    int left=0, right=max_len, ans=max_len; 

    while(left <= right){
        int mid = (left+right)>>1; 
        if(check(mid)){
            ans = mid; 
            right = mid-1; 
        }else{
            left = mid+1; 
        }
    }
    cout<<ans; 
    i_ak ioi; 
}

复杂度分析：O((n+m)\log n)。

亲测可过，请勿抄袭！