参照第二篇题解的说法

#include <bits/stdc++.h>
#define MAXN 100100
using namespace std;
int n,m,s[MAXN],t[MAXN],sum[MAXN];
struct edge{
	int v,w;
};
vector <edge> G[MAXN];
void add(int u,int v,int w)//建树 
{
	G[u].push_back((edge){v,w});
	G[v].push_back((edge){u,w});
}
void dfs(int u,int fa,int t)//dfs求点与点之间路径的权值和以及最长的边 
{
	int length=0,max_len=0;//边权和 最长边 
	if(u==t)//到达终点 
	{
		cout << length-max_len << endl;//答案 
		return;
	}
	for(int i=0;i<=G[u].size();i++)
	{
		int to=G[u][i].v;
		if(to==fa)
			continue;
		dfs(to,u,t);
		length+=G[u][i].w;//更新 
		max_len=max(max_len,G[u][i].w);
	}
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n-1;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		sum[v]=sum[u]+w;//全是链的话，用前缀和优化计算边权和的过程 
		add(u,v,w);
	}
	for(int i=1;i<=m;i++)
		cin >> s[i] >> t[i];
	if(m==1) 
		dfs(s[1],0,t[1]);
	else//全是链的情况 
	{
		int answer=0;//答案 
		for(int i=1;i<=n-1;i++)//枚举每一个边，暴力删边 
		{
			int res=0,wor=G[i][i+1].w;
			G[i][i+1].w=0;//删边 
			for(int j=1;j<=m;j++)
			{
				int tot=abs(sum[t[j]]-sum[s[j]]);
				if(i<=t[i] && i>=s[j])
					tot-=wor;
				res=max(res,tot);
				//找出最长链即为目前所需时间 
			}
			G[i][i+1].w=wor;//类似回溯 
			answer=min(answer,res);//更新 
		}
		cout << answer << endl;
	}
	return 0;
}