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

· · 题解

背景：学习 LCA 时的练习题，被卡了整整两天，于是发篇题解巩固一下。

题意简述：

改其中一条边使其改为虫洞（即改权值为 0），使得所有运输计划的时间的最大值最小。

思路：

二分，倍增与树上差分。

考虑二分答案，设所有运输计划的时间的最大的最小值为 k，判断是否能够改一条边权值为 0 使得所有运输路径的权值小于等于 k。

首先可以将运输计划分类：

  1. 路径权值小于 k；
  2. 路径权值大于 k。

改造的边一定是在第二类运输计划的路径的公共边上，否则不可能使所有运输路径的权值小于等于 k，因为这一条边不在其中一个第二类运输计划的路径上，那么这一个运输计划就不会改变路径权值之和。

接下来考虑如何选择边。用一个数组记录 x 与它父节点组成的边被覆盖的次数，当然不能直接算，这里用差分优化。最终被覆盖的总次数为第二种运输计划的数量就是可以选择修改的边。

求出所有可以修改的边的最大权值，再判断最大的运输路径的权值和减去可以修改的边的最大权值是否小于等于 k。

最后，求路径权值和肯定不能暴力，可以用一个数组记录从根节点到当前节点的权值和，再预处理一个倍增表，就可以比较快速求出两点之间的路径权值和。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=300005;
int n,m,maxpllen;
struct node{
    int x,w;
};
vector<node>a[N];//领接表存边
int fath[N][30];//倍增表
int lg[N],deep[N],dis[N];//lg[i]=log2(i),deep[i]为i在树中的深度，dis[i]表示根节点到节点i的权值和
int num[N],lca[N],pldis[N];//num为差分数组，lca[i]为第i个运输计划的两点的最近公共祖先,pldis[i]为第i个运输计划的路径权值之和
struct plan{
    int s,t;
}pl[N];//运输计划
void dfs(int x,int fa){//预处理
    deep[x]=deep[fa]+1;
    fath[x][0]=fa;
    int len=a[x].size();
    for(int i=0;i<len;i++){
        int y=a[x][i].x;
        if(y==fa)continue;
        dis[y]=dis[x]+a[x][i].w;
        dfs(y,x);
    }
}int LCA(int x,int y){//求最近公共祖先
    if(deep[x]<deep[y])swap(x,y);
    while(deep[x]>deep[y])x=fath[x][lg[deep[x]-deep[y]]];
    if(x==y)return x;
    for(int i=lg[deep[x]];i>=0;i--)
        if(fath[x][i]!=fath[y][i])x=fath[x][i],y=fath[y][i];
    return fath[x][0];
}void dfs2(int x,int fa){//树上差分
    int len=a[x].size();
    for(int i=0;i<len;i++){
        int y=a[x][i].x;
        if(y==fa)continue;
        dfs2(y,x);
        num[x]+=num[y];
    }
}bool check(int x){//二分判断
    //cout<<"\n------\n"<<x<<endl;
    memset(num,0,sizeof(num));
    int cnt=0,maxlen=0;
    for(int i=1;i<=m;i++){
        int pllen=pldis[i];
        if(pllen>x){//第二种运输计划
            num[pl[i].s]++;//差分处理
            num[pl[i].t]++;
            num[lca[i]]-=2;
            cnt++;
        }maxlen=max(maxlen,pllen);
    }if(cnt==0)return true;//没有第二种运输计划则满足
    dfs2(1,0);//用差分还原出原数组
    /*cout<<x<<endl;
    for(int i=1;i<=n;i++)cout<<num[i]<<" ";
    cout<<endl;*/
    for(int i=2;i<=n;i++){//是否有满足条件的
        if(num[i]!=cnt)continue;
        if(maxlen-(dis[i]-dis[fath[i][0]])<=x)return true;
    }return false;
}
signed main(){
    scanf("%lld%lld",&n,&m);int l=0,r=0,mid;
    for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
    for(int i=1,x,y,w;i<n;i++){
        scanf("%lld%lld%lld",&x,&y,&w);
        a[x].push_back(node{y,w});
        a[y].push_back(node{x,w});
        l=max(l,w);
    }dfs(1,0);
    for(int i=1;i<=lg[n];i++)//预处理倍增表
        for(int j=1;j<=n;j++)
            fath[j][i]=fath[fath[j][i-1]][i-1];
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&pl[i].s,&pl[i].t);
        lca[i]=LCA(pl[i].s,pl[i].t);
        pldis[i]=dis[pl[i].s]+dis[pl[i].t]-dis[lca[i]]*2;
        r=max(r,pldis[i]);
    }maxpllen=r;
        /*for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cout<<LCA(i,j)<<" ";
            }cout<<endl;
        }*/
    l=r-l;while(l<r){//二分答案
        mid=l+r>>1;
        check(mid)?r=mid:l=mid+1;
    }cout<<r;
    return 0;
}