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

· · 题解

题目大意

选择一条边，把它的边权改为 0 使得走完所有给定路径的最大值最小。

Solutoin

本题是最大值最小的问题，我们可以想到二分，二分完成所有工作的最短时间 mid。
那么判断如果所有不合法的路径，即通过这条路径的时间大于 mid 的路径，都通过一条边，且权值和最大的路径减这条边的边权小于 mid，那么 mid 是合法的。
实现的时候可以使用树上差分来统计是否所有非法路径都通过同一条边。

代码时间

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int n,m,fa[N],dep[N],son[N],top[N],sum[N],sz[N],st[N],en[N],temp[N],dfn[N];
vector<pair<int,int> > e[N];
void dfs(int x,int deep,int father,int val)
{
    sz[x]=1,dep[x]=deep,fa[x]=father,sum[x]=val;
    for(auto v:e[x])
    {
        int u=v.first,w=v.second;
        if(u==fa[x]) continue;
        dfs(u,deep+1,x,val+w);
        sz[x]+=sz[u];
        if(sz[u]>sz[son[x]]) son[x]=u;
    }
}
int tot;
void dfs1(int x,int k)
{
    dfn[++tot]=x;
    if(son[x]) dfs1(son[x],k);
    top[x]=k;
    for(auto v:e[x])
    {
        int u=v.first;
        if(u==son[x]||u==fa[x]) continue;
        dfs1(u,u);
    }
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];)
    {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return (dep[x]<dep[y])?x:y;
}
bool check(int x)
{
    int sm=0,maxx=0;
    memset(temp,0,sizeof temp);
    for(int i=1;i<=m;i++)
    {
        int LCA=lca(st[i],en[i]);
        if(sum[st[i]]+sum[en[i]]-2*sum[LCA]<=x) continue; 
        maxx=max(maxx,sum[st[i]]+sum[en[i]]-2*sum[LCA]-x);
        temp[st[i]]++,temp[en[i]]++;
        temp[LCA]-=2;
        sm++;
    }
    if(!sm) return true;
    for(int i=n;i>1;i--) temp[fa[dfn[i]]]+=temp[dfn[i]];
    for(int i=1;i<=n;i++)
    {
        if(temp[dfn[i]]>=sm&&sum[dfn[i]]-sum[fa[dfn[i]]]>=maxx) return true;
    }
    return false;
}
int f(int l,int r)
{
    if(l>=r) return l;
    int mid=l+r>>1;
    if(check(mid)) return f(l,mid);
    return f(mid+1,r);
}
int main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int sm=0;
    for(int i=1;i<n;i++) 
    {
        int x,y,z;
        cin>>x>>y>>z;
        e[x].push_back({y,z});
        e[y].push_back({x,z});
        sm+=z;
    }
    for(int i=1;i<=m;i++) cin>>st[i]>>en[i];
    dfs(1,1,0,0);
    dfs1(1,1);
    cout<<f(0,sm);
    return 0;
}