AC（有问题找我）

#include<bits/stdc++.h>
#define dd(i) dis[a[i]]+dis[b[i]]-dis[lca[i]]*2
using namespace std;
const int maxn=3e5+5;
int top[maxn],fa[maxn],mxson[maxn],siz[maxn],dep[maxn],head[maxn],id[maxn],a[maxn],b[maxn],lca[maxn],dis[maxn],ww[maxn],cf[maxn];
struct sd{
    int to,next,w;
}edge[maxn*2];
int cnt,n,m,mx1,mx2;
void add(int from,int to,int w1)
{
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    edge[cnt].w=w1;
    head[from]=cnt;
}
void dfs(int v,int ff,int deep)
{
    id[++cnt]=v,fa[v]=ff,dep[v]=deep,siz[v]=1;
    int MS=0,MX=0;
    for(int i=head[v];i!=0;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to!=ff)
        {
            ww[to]=edge[i].w;
            dis[to]=dis[v]+ww[to];
            dfs(to,v,deep+1);
            if(MX<siz[to]) MX=siz[to],MS=to;
            siz[v]+=siz[to];
        }
    }
    mxson[v]=MS;
}
void dfs2(int v,int tt)
{
    top[v]=tt;
    if(!mxson[v]) return;
    dfs2(mxson[v],tt);
    for(int i=head[v];i!=0;i=edge[i].next)
    {
        if(edge[i].to!=fa[v]&&edge[i].to!=mxson[v])
            dfs2(edge[i].to,edge[i].to);
    }
}
int LCA(int a,int b)
{
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]]) a=fa[top[a]];
        else b=fa[top[b]];
    }
    if(dep[a]<dep[b]) return a;
    else return b;
}
bool check(int k)
{
    memset(cf,0,sizeof(cf)),cnt=0;
    for(int i=1;i<=m;i++)
    if(dd(i)>k) cf[a[i]]++,cf[b[i]]++,cf[lca[i]]-=2,cnt++;
    for(int i=n;i>=1;i--)
    {
        cf[fa[id[i]]]+=cf[id[i]];
        if(ww[id[i]]>=mx2-k&&cf[id[i]]==cnt) return true;
    }
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int a1,b1,w1;
        scanf("%d%d%d",&a1,&b1,&w1);
        add(a1,b1,w1);add(b1,a1,w1);
        mx1=max(mx1,w1);
    }
    cnt=0,dfs(1,0,1),dfs2(1,1);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        lca[i]=LCA(a[i],b[i]);
        mx2=max(dd(i),mx2);
    }
    int l=mx2-mx1,r=mx2+1,ans;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
    }
    printf("%d",ans);
    return 0;
}