(LCA,树上差分,二分)O((N+ M)logT)

如果可以在$t$时间内完成，则一定可以在大于$t$的时间内完成，因此可以二分答案。

时间确定之后，原问题变成一个判定性问题:是否可以通过去掉一条边，使所有路径的总长度在$t$以内。

此时去掉所有长度大于$t$的路径的最长公共边一定是最优的。

那怎么找出所有公共边呢?我们可以将每条路径上的所有边加1，最后判断每条边上的总和是否等于路径总数即可

最后的问题是如何快速求树上某一条路径的和，以及给某个路径加上相同数呢?这里可以借鉴前缀和和差分的思想。在树上做前缀和和差分的时候需要先求路径两个端点的最近公共祖先，求LCA的方式有很多，这里采用的是倍增的方式。

#include<bits/stdc++.h>
using namespace std;
const int N=300010,M=N*2,K=19;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int fa[N][K],dep[N],dist[N],seq[N],cnt;
int sum[N];//差分
struct Path{
    int a,b,p,d;
}q[N];
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dfs(int u,int father,int depth)
{
    seq[cnt++]=u; //dfs序列
    dep[u]=depth; //记录深度
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==father) continue;
        fa[j][0]=u; 
        for(int k=1;k<K;k++) //更新j可以走到的节点
        {
            fa[j][k]=fa[fa[j][k-1]][k-1];
        }
        dist[j]=dist[u]+w[i]; //更新当前点到根节点的距离
        dfs(j,u,depth+1); //继续搜索后续节点
    }
}
int lca(int a,int b)
{
    if(dep[a]<dep[b]) swap(a,b); //保证a的深度小于等于b的深度
    for(int k=K-1;k>=0;k--) //跳到同一深度
    {
        if(dep[fa[a][k]]>=dep[b])
        {
            a=fa[a][k];
        }
    }
    if(a==b) return a; //找到公共祖先
    for(int k=K-1;k>=0;k--) //跳到公共祖先的下个位置
    {
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    }
    return fa[a][0]; //返回公共祖先
}
bool check(int mid)
{
    memset(sum,0,sizeof sum); //清空差分数组
    int c=0,max_d=0;//边数和最大路径
    for(int i=0;i<m;i++)
    {
        int a=q[i].a,b=q[i].b,p=q[i].p,d=q[i].d;
        if(d>mid)
        {
            c++;
            max_d=max(max_d,d);
            sum[a]++,sum[b]++,sum[p]-=2;//差分数组维护序列
        }
    }
    if(!c) return true;//没有超过mid的边
    for(int i=n-1;i>=0;i--)
    {
        int j=seq[i]; //找到dfs序的第i个点
        sum[fa[j][0]]+=sum[j];//累加差分数组
    }
    for(int i=1;i<=n;i++)
    {
        if(sum[i]==c&&max_d-(dist[i]-dist[fa[i][0]])<=mid)
        {
            return true;
        }
    }
    return false; //找不到
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1,1);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        int d=dist[a]+dist[b]-dist[p]*2; //计算路径
        q[i]={a,b,p,d};
    }
    int l=0,r=3e8;
    while(l<r) //二分最小值
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l;
    return 0;
}