本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-14 14:40:43

思路

如果能在 $t_1$ 的时间内解决，那么一定能在 $t_2 (t_2 \ge t_1)$ 的时间内解决。
所以可以二分最短时间。
那如何写 check 呢
设 check 的任务是判断能否在 $t$ 时间内解决，把 $m$ 个运输计划看成树上的 $m$ 条链。

1. 计算出长度最大的链，将其长度设为 $imax$
2. 算出有多少条链的长度大于 $t$，设为 $sum$
3. 求树上每个边被（长度大于 $t$ 的链）经过的次数。
4. 计算出边权最大的（被（长度大于 $t$ 的链）经过的次数等于 $sum$ 的边），将其边权设为 $w$
5. 判断删除（步骤 4 求出的边）之后能否在 $t$ 时间内解决

解释：

• 步骤 4 中，某条边被经过次数等于 $sum$，意思就是说这条边被所有（长度大于 $t$ 的链）经过，就是在找最大公共边
• 步骤 5 的求解方法：如果 $imax - w \le t$，那么可以在 $t$ 时间内解决，否则不可以

另外，求链长可以 lca 求出，另外对于一条边，它对应它的起点 $u$ 和终点 $t$ 中深度大的点。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	const int maxn=300005;
	int n,m;
	int head[maxn];
	struct EDGE
	{
		int to,val,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to,int val)
	{
		edge[++cnt].to=to;
		edge[cnt].val=val;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int fa[20][maxn];
	int dep[maxn];\/\/每个点的深度 
	int dis[maxn];\/\/每个点到根节点的距离 
	int imax;\/\/最长的链的长度 
	int node_to_edge[maxn];
	void dfs(int u,int _fa)
	{
		fa[0][u]=_fa;
		dep[u]=dep[_fa]+1;
		for(int i=1;i<=19;i++)
		{
			fa[i][u]=fa[i-1][fa[i-1][u]];
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			node_to_edge[to]=i;
			dis[to]=dis[u]+edge[i].val;
			dfs(to,u);
		}
	}
	inline int lca(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		for(int i=19;i>=0;i--)
		{
			if(dep[fa[i][x]]>=dep[y])
			{
				x=fa[i][x];
			}
		}
		if(x==y)return x;
		for(int i=19;i>=0;i--)
		{
			if(fa[i][x]!=fa[i][y])
			{
				x=fa[i][x];
				y=fa[i][y];
			}
		 } 
		 return fa[0][x];
	}
	struct Question
	{
		int u,v,len;
	}q[maxn];
	int cf[maxn]; 
	inline int get_dis(int a,int b)
	{
		int _lca=lca(a,b);
		return dis[a]+dis[b]-2*dis[_lca];
	}
	int sum,w;
	void dfs2(int u,int _fa)
	{
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==_fa)continue;
			dfs2(to,u);
			cf[u]+=cf[to];
		}
		if(cf[u]==sum)
		{
			w=max(w,edge[node_to_edge[u]].val);
		}
	}
	inline bool check(int t)
	{
		sum=w=0;
		for(int i=1;i<=m;i++)
		{
			if(q[i].len>t)
			{
				sum++;
				cf[q[i].u]++;
				cf[q[i].v]++;
				cf[lca(q[i].u,q[i].v)]-=2;
			}
		}
		dfs2(1,0);
		for(int i=1;i<=n;i++)
		{
			cf[i]=0;
		}
		if(imax-w<=t)return 1;
		return 0;
	}
	void main()
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<n;i++)
		{
			int ai,bi,ti;
			scanf("%d%d%d",&ai,&bi,&ti);
			add(ai,bi,ti);
			add(bi,ai,ti);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&q[i].u,&q[i].v);
			q[i].len=get_dis(q[i].u,q[i].v);
		}
		for(int i=1;i<=m;i++)
		{\/\/求最大链长 
			imax=max(imax,q[i].len);
		}
		int l=0,r=imax;
		while(l<r)
		{
			int mid=(l+r)>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		printf("%d",l);
	}
}
int main()
{
	Main::main();
	return 0; 
}

参考博客

1. communist 的博客
2. CodyTheWolf 的博客