前言

运输计划这道题作为当年 NOIP 的 D2T3，是一道卡常好题。没有用什么高级的算法，重点在于思路。

分析

题意不再赘述。我们要求：完成阶段性工作所需要的时间最短，换个说法，即所有计划中所用时间最长的需要最短。我们提取出关键词“最长的最短”，这提示我们可以二分！

接下来考虑二分如何验证。比如验证能否在 $k$ 时间内完成。若要在 $k$ 时间内完成，则原本完成时间大于 $k$ 的计划中必须有航道被改造。也就是说，我们必须将一条被所有完成时间大于 $k$ 的计划覆盖的航道改为虫洞，并且这条航道的长度必须大于等于计划最大路径长度减 $k$，阶段性工作才能在 $k$ 时间内完成。

求所有完成时间大于 $k$ 的计划，用 LCA 计算路径长度即可； 求满足被所有完成时间大于 $k$ 的计划覆盖的航道，可以使用树上差分。但我们要把路径转化到点上 —— 令 1 为根，将路径转到子节点上存储，以便差分。时间复杂度 $O(n\log n)$。

接下来如果被卡常了，可能是差分后做树上前缀和的那个 dfs 太慢。怎么办呢？我们在 LCA 预处理时同时存入遍历节点的顺序，就可以倒序遍历这个数组做 $dp_{fa_x} \gets dp_x$，不用 dfs 了。显然，这样做前缀和是正确的。

代码

有注释。

#include<bits/stdc++.h>
#define i128 __int128
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define Pii pair<int,int>
#define fi first
#define se second
#define inline
#define f(x,y) fixed<<setprecision(y)<<x
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,rp,stdin),p1==p2)?EOF:*p1++)

using namespace std;
const int N=3e5+10;
const int rp=1e6+10;

int n,m,cnt,ans,dis[N],dp[N];
int dep[N],fa[N],siz[N],son[N],top[N],dfn[N];//树剖
struct node{int u,v,w;}e[N];//存边
struct ask{int u,v,w,t;}p[N];//存航线的起终点、lca、长度
vector<Pii> vt[N];
char buf[rp],*p1=buf,*p2=buf;

inline int read()
{
	int x=0,f=1; char c=0;
	while(!isdigit(c)) {if(c=='-') f=-1; c=gc();}
	while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=gc();
	return x*f;
}

inline char read_ch()
{
	char c=0;
	while((!isalpha(c))&&(!isdigit(c))) c=gc();
	return c;
}

inline void dfs1(int x,int f)
{
	dep[x]=dep[f]+1; fa[x]=f; siz[x]=1; dfn[++cnt]=x;//存入遍历节点的顺序
	for(auto a:vt[x])
		if(a.fi!=f)
		{
			dis[a.fi]=dis[x]+a.se;
			dfs1(a.fi,x); siz[x]+=siz[a.fi];
			if(siz[a.fi]>siz[son[x]]) son[x]=a.fi;
		}
}

inline void dfs2(int x,int tp)
{
	top[x]=tp;
	if(!son[x]) return; dfs2(son[x],tp);
	for(auto a:vt[x])
		if(a.fi!=fa[x]&&a.fi!=son[x]) dfs2(a.fi,a.fi);
}//树剖两个 dfs 预处理

inline int lca(int u,int v)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	return u;
}//树剖求 lca

inline bool cr(int x)
{
	int cnt=0,res=0; memset(dp,0,sizeof dp);
	for(int i=1;i<=m;++i)
		if(p[i].t>x)//完成时间大于当前二分答案的计划数量加一
		{
			++cnt; res=max(res,p[i].t); dp[p[i].w]-=2;
			++dp[p[i].u]; ++dp[p[i].v];//树上差分
		}
	if(!cnt) return 1;
	for(int i=n;i>=1;--i) dp[fa[dfn[i]]]+=dp[dfn[i]];//倒序前缀和
	for(int i=1;i<n;++i)
		if(dp[e[i].u]==cnt&&res-e[i].w<=x) return 1;
	return 0;
}

signed main()
{
	cin.tie(0)->sync_with_stdio(0);
	cin>>n>>m; int L=0,R=5e8,mi;
	for(int i=1;i<n;++i)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
		vt[e[i].u].push_back({e[i].v,e[i].w});
		vt[e[i].v].push_back({e[i].u,e[i].w});
	}
	for(int i=1;i<=m;++i) cin>>p[i].u>>p[i].v;
	dfs1(1,0); dfs2(1,1);
	for(int i=1;i<n;++i)
		if(dep[e[i].u]<dep[e[i].v]) swap(e[i].u,e[i].v);
	for(int i=1;i<=m;++i)
		p[i].w=lca(p[i].u,p[i].v),
		p[i].t=dis[p[i].u]+dis[p[i].v]-dis[p[i].w]-dis[p[i].w];//先处理出来
	while(L<=R)//二分
	{
		mi=(L+R)>>1;
		if(cr(mi)) R=mi-1,ans=mi;
		else L=mi+1;
	}
	cout<<ans;
	return 0;
}