题目描述

L 国有 n 个星球, 还有 n-1 条双向航道, 每条航道建立在两个星球之间, 这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司, 该公司有很多个运输计划, 每个运输计划形如: 有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然, 飞船驶过一条航道 是需要时间的, 对于航道 j, 任意飞船驶过它所花费的时间为 tj, 并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设, 即允许小 P 把某一条航道改造成虫洞, 飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始, 所有飞船一起出发。当这 m 个运输计划都完成时, 小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞, 试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

题目分析

首先我们可以求出每一条路径长度，这个倍增求个 lca，每个点到根节点距离 dfs 预处理即可。
接下来就不知道如何下手了对不对？

在不知道下一步该怎么办的情况下可以考虑二分答案。 ——沃·兹基朔德

好吧，那就二分答案吧。我们可以找出 k 条路径长度大于当前二分出的答案，所以要变成虫洞的那一条边一定会是这若干路径的交边。
于是我们使用树上差分和将每条边的影响落到终点的思想，即在路径两个端点处+1，在 lca 处-2。然后处理这个值。
这么处理：

void find(int x,int las){
    for(int i=h[x];i!=-1;i=ne[i]){
        if(to[i]==las)continue;
        find(to[i],x),js[x]+=js[to[i]];
    }
}

获得的 js 值就是这条边在这若干个路径里经过的次数。然后选择边权最大的交边，看我们二分出来的答案是否可行即可。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
const int N=300005;
int n,m,tot;
int h[N],ne[N<<1],to[N<<1],l[N<<1];
int dis[N],f[N][22],dep[N],js[N];
struct node{int s,t,lon,o;}a[N];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,l[tot]=z;}
void dfs(int x,int las,int lon,int d){
    int i;dep[x]=d,dis[x]=lon,f[x][0]=las;
    for(i=1;i<=20;++i)f[x][i]=f[f[x][i-1]][i-1];
    for(i=h[x];i!=-1;i=ne[i])
        if(to[i]!=las)dfs(to[i],x,lon+l[i],d+1);
}
int lca(int x,int y){
    int i;if(dep[x]<dep[y])swap(x,y);
    for(i=20;i>=0;--i)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(i=20;i>=0;--i)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
void find(int x,int las){
    for(int i=h[x];i!=-1;i=ne[i]){
        if(to[i]==las)continue;
        find(to[i],x),js[x]+=js[to[i]];
    }
}
int check(int lim){
    int i,cnt=0,mx=0;
    for(i=1;i<=n;++i)js[i]=0;//树前缀和，s 和 t 都+1,o 要-2, 边的经过次数落到终点上的思想
    for(i=m;i>=1;--i){
        if(a[i].lon<=lim)break;++cnt;
        ++js[a[i].s],++js[a[i].t],js[a[i].o]-=2;
    }
    find(1,0);
    for(i=1;i<=n;++i)
        if(js[i]==cnt)mx=max(mx,dis[i]-dis[f[i][0]]);
    if(a[m].lon-mx<=lim)return 1;
    else return 0;
}
bool cmp(node x,node y){return x.lon<y.lon;}
int main(){
    int i,j,l=0,r=0,mid,ans,x,y,z;
    n=read(),m=read();
    for(i=1;i<=n;++i)h[i]=-1;
    for(i=1;i<n;++i){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
    dfs(1,0,0,1);
    for(i=1;i<=m;++i){
        a[i].s=read(),a[i].t=read();a[i].o=lca(a[i].s,a[i].t);
        a[i].lon=dis[a[i].s]+dis[a[i].t]-2*dis[a[i].o];
        r=max(r,a[i].lon);
    }
    sort(a+1,a+1+m,cmp);
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}