题目

题解：

大佬的博客
思路其实很简单，就是tarjan求lca+二分答案+树上差分（貌似不需要解释，看到这个思路就应该基本上会写了吧），实现起来也听简单的

#include<bits/stdc++.h>
using namespace std;
const int N=300003;
struct node{
    int to,w,ne;
}e[N<<1],q[N<<1];
struct kk{
    int u,v,lca,len;
}len[N];
int h[N],head[N],tot,cnt,ret,f[N],mx,i,l,r,mid,s[N],ans,dis[N],a[N],vis[N],num,n,m,x,y,z;
int read(){
    char c;int x=0,f=1;
    do{c=getchar();if(c=='-')f=-1;}while(c<48||c>57);
    do x=(x<<1)+(x<<3)+(c^48),c=getchar();while(c>=48&&c<=57);
    return f*x;
}
void add(int x,int y,int z){
    e[++tot]=(node){y,z,h[x]};
    h[x]=tot;
}
void addq(int x,int y){
    q[++cnt]=(node){y,0,head[x]};
    head[x]=cnt;
}
int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);
}
void tarjan(int u,int pre){
    for (int i=h[u],v;i;i=e[i].ne)
        if ((v=e[i].to)!=pre){
            dis[v]=dis[u]+e[i].w;
            tarjan(v,u);
            a[v]=e[i].w;
            int rx=find(v),ry=find(u);
            if (rx!=ry) f[rx]=ry;
            vis[v]=1;
        }
    for (int i=head[u],p,v;i;i=q[i].ne)
        if (vis[v=q[i].to]){
            p=(i+1)>>1;
            len[p].lca=find(v);
            len[p].len=dis[u]+dis[v]-2*dis[len[p].lca];
            mx=max(mx,len[p].len);
        }
}
void dfs(int u,int pre){
    for (int i=h[u],v;i;i=e[i].ne)
        if ((v=e[i].to)!=pre) dfs(v,u),s[u]+=s[v];
    if (s[u]==num) ret=max(ret,a[u]);
}
bool check(int x){
    num=ret=0;
    memset(s,0,sizeof(s));
    for (int i=1;i<=m;i++)
        if (len[i].len>x) s[len[i].u]++,s[len[i].v]++,s[len[i].lca]-=2,num++;
    dfs(1,0);
    return mx-ret<=x;
}
int main(){
    n=read();m=read();
    for (i=1;i<n;i++) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    for (i=1;i<=n;i++) f[i]=i;
    for (i=1;i<=m;i++) len[i].u=x=read(),len[i].v=y=read(),addq(x,y),addq(y,x);
    tarjan(1,0);
    l=0;r=mx;
    while (l<=r){
        mid=l+r>>1;
        if (check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%d",ans);
}