闲话：虽说是紫题，但慢慢想还是完全没有问题的。
由于 \(m\) 个运输计划同时开始，所以耗费时间就是最慢的飞船耗费的时间（即最长时间）。考虑到题目让求最短时间，也就是最长的最短，可以二分。
考虑二分最长时间（记作 \(k\)），那么将所有路径分成两类，一类是原来耗费的时间就小于等于 \(k\) 的，这部分路径不用处理；另一类则相反，需要将某一条边的权值变成 \(0\)，判断是否合法，计算耗费的时间可以用边前缀和。那么肯定要找出不合法路径的公共边，由于只能修改一条边权，所以如果不合法边没有 \(\ge 1\) 条公共边，是不可能符合要求的。对于查找公共边，我的做法是：先将不合法边进行边差分，跑一遍自底向上的 \(dfs\) 求每条边的经过次数，若经过次数等于不合法边的数量，则成立。
找出公共边后，贪心的思考，肯定要将其中最大的边去掉，在找一遍最大的边，与最大的不合法路径相减判断即可。
由于本题卡常，对于 \(LCA\) 部分需写树剖预处理，本人使用倍增，故只拿 \(90\) 分。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') { if(c=='-') flag=-1; c=getchar(); }
while(c>='0'&&c<='9') { sum=sum*10+c-'0'; c=getchar(); }
return sum*flag;
}
const int N=3e5+10;
int n,m;
int u[N],v[N];
int a[N],b[N],c[N],t[N];
int tot,to[N<<1],nxt[N<<1],h[N],w[N<<1],tag[N<<1];
int dep[N],f[N][21];
int diff[N],sdf[N];
int sum[N];
void add(int x,int y,int z,int k) {
to[++tot]=y; w[tot]=z; tag[tot]=k;
nxt[tot]=h[x]; h[x]=tot;
}
void dfs1(int nd,int fa) {
dep[nd]=dep[fa]+1;
for(int i=0;i<=19;i++) f[nd][i+1]=f[f[nd][i]][i];
for(int i=h[nd];i;i=nxt[i]) {
int x=to[i];
if(x==fa) continue;
f[x][0]=nd;
sum[x]=sum[nd]+w[i];
dfs1(x,nd);
}
}
int LCA(int x,int y) {
if(dep[x]<dep[y]) {
swap(x,y);
}
for(int i=20;i>=0;i--) {
if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
}
for(int 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 dfs2(int nd,int fa) {
sdf[nd]=diff[nd];
for(int i=h[nd];i;i=nxt[i]) {
int x=to[i];
if(x==fa) continue;
dfs2(x,nd);
sdf[nd]+=sdf[x];
c[tag[i]]=sdf[x];
}
}
int check(int k) {
for(int i=0;i<=n;i++) {
diff[i]=0; sdf[i]=0; c[i]=0;
}
int maxn=0,cnt=0;
for(int i=1;i<=n-1;i++) {
int x=u[i],y=v[i],lca=LCA(u[i],v[i]);
int he=sum[x]+sum[y]-2*sum[lca];
if(he<=k) continue;
maxn=max(maxn,he); cnt++;
diff[x]++; diff[y]++; diff[lca]-=2;
}
dfs2(1,0);
int max2=0;
for(int i=1;i<=n-1;i++) {
if(c[i]==cnt) {
max2=max(max2,t[i]);
}
}
if(maxn-max2<=k) return 1;
return 0;
}
int main() {
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n-1;i++) {
a[i]=read(); b[i]=read(); t[i]=read();
add(a[i],b[i],t[i],i);
add(b[i],a[i],t[i],i);
}
dfs1(1,0);
for(int i=1;i<=m;i++) {
u[i]=read(); v[i]=read();
}
int l=0,r=1e9;
while(l<r) {
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r;
return 0;
}