1 #include<iostream>  2 #include<cstring>  3 #include<cstdio>  4 #include<algorithm>  5 using namespace std;  6 int read()  7 {  8     int x=0,f=1;char ch;ch=getchar();  9     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}  10     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}  11     return x*f; 12 } 13 struct data{int to,next,v,from;}e[600001]; 14 struct data2{int to,next,from,num;}as[600001]; 15 int lca[300001],dis[300001]; 16 int head[300001],head2[300001],cnt; 17 void add(int u,int v,int w){e[cnt].from=u,e[cnt].to=v,e[cnt].next=head[u],e[cnt].v=w,head[u]=cnt;cnt++;} 18 void add2(int u,int v,int nu){as[cnt].to=v,as[cnt].next=head2[u],as[cnt].from=u,as[cnt].num=nu,head2[u]=cnt,cnt++;} 19 int n,m,l=0,r=0; 20 int d[300001]; 21 bool vis[300001]; 22 int fa[300001]; 23 int p[300001]; 24 int s[300001],t1[300001]; 25 int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);} 26 int maxn=0,maxj=0; 27 void dfs(int now,int d) 28 { 29     dis[now]=d; 30     vis[now]=1; 31     for(int i=head[now];i>=0;i=e[i].next) if(!vis[e[i].to]) dfs(e[i].to,d+e[i].v); 32 } 33 void Lca(int now) 34 { 35     vis[now]=1; 36     for(int i=head[now];i>=0;i=e[i].next) 37         if(!vis[e[i].to]) 38         { 39             Lca(e[i].to);fa[find(e[i].to)]=find(now); 40         } 41     for(int i=head2[now];i>=0;i=as[i].next) 42     { 43         if(vis[as[i].to]) 44         { 45             lca[as[i].num]=find(as[i].to); 46             //cout<<dis[as[i].from]<<‘ ‘<<dis[as[i].to]<<‘ ‘<<2*dis[lca[as[i].num]]<<endl; 47             d[as[i].num]=abs(dis[as[i].from]+dis[as[i].to]-2*dis[lca[as[i].num]]); 48             r=max(r,d[as[i].num]); 49         } 50     } 51 } 52 int work(int now,int t,int from) 53 { 54     int sum=p[now]; 55     for(int i=head[now];i>=0;i=e[i].next) 56         if(e[i].to!=from) sum+=work(e[i].to,t,e[i].from); 57     if(sum==t)maxj=max(maxj,dis[now]-dis[from]); 58     return sum; 59 } 60 bool check(int mid,int t) 61 { 62     work(1,t,0); 63     if(maxn-maxj<=mid) return 1; 64     else return 0; 65 } 66 int main() 67 { 68     memset(head,-1,sizeof(head)); 69     memset(head2,-1,sizeof(head2)); 70     n=read(),m=read(); 71     for(int i=1;i<=n;i++) fa[i]=i; 72     for(int i=1;i<n;i++) 73     { 74         int u,v,w; 75         u=read(),v=read(),w=read(); 76         add(u,v,w); 77         add(v,u,w); 78     } 79     cnt=0; 80     for(int i=1;i<=m;i++) 81     { 82         s[i]=read(),t1[i]=read(); 83         add2(s[i],t1[i],i); 84         add2(t1[i],s[i],i); 85     } 86     dfs(1,0); 87     memset(vis,0,sizeof(vis)); 88     Lca(1); 89     //for(int i=1;i<=n;i++) cout<<dis[i]<<endl; 90     //for(int i=1;i<=m;i++) cout<<d[i]<<endl; 91     while(l<=r) 92     { 93         int t=0; 94         int mid=(l+r)>>1; 95         maxj=0; 96         memset(p,0,sizeof(p)); 97         for(int i=1;i<=m;i++) 98         { 99             if(d[i]>mid){maxn=max(maxn,d[i]);t++;p[s[i]]++,p[t1[i]]++,p[lca[i]]-=2;}100         }101         if(check(mid,t)) r=mid-1;102         else l=mid+1;103     }104     cout<<l;105     return 0;106 }