#include <bits/stdc++.h>
#define pii pair<int,int>  
#define maxn 300010
#define maxk 25
#define runk 19
using namespace std;
int fa[maxn][maxk];
int depth[maxn];
vector<pii> g[maxn];
int n,m;
int p[maxn];
int a[maxn],b[maxn];
pii t[maxn];
void dfs(int u,int f){
	depth[u] = depth[f]+1;fa[u][0] = f;
	for(int i = 1;i<=runk;i++) fa[u][i] = fa[fa[u][i-1]][i-1];
	for(int i = 0;i<g[u].size();i++){
		int v = g[u][i].first;
		if(v==f) continue;
		p[v] = p[u]+g[u][i].second;
		dfs(v,u);
	}
}
int LCA(int x,int y){
	if(depth[x]<=depth[y]) swap(x,y);
	for(int i = runk;i>=0;i--) if(depth[fa[x][i]]>=depth[y]) x = fa[x][i];
	if(x==y) return x;
	for(int i = runk;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x = fa[x][i],y = fa[y][i];
		}
	}
	return fa[x][0];
}
int dict(int x,int y){
	return p[x]+p[y]-2*p[LCA(x,y)];
}
bool check1(int x,int y,int z,int s){
	int father = LCA(z,s);
	int high = LCA(x,y);
	high = z==high?s:z;
	if(LCA(x,father)==father and LCA(y,father)==father and (LCA(z,high)==high or LCA(y,high)==high)){
//		cout<<x<<" "<<y<<" "<<z<<" "<<s<<" "<<father<<endl;
		return 1;
	} 
	else return 0;
}
bool check(int length){
	for(int i = 1;i<n;i++){
		int cnt = 0;bool flag;
		for(int j = 1;j<=m;j++){
			int f = depth[a[j]]>depth[b[j]]?b[j]:a[j],s = depth[a[j]]>depth[b[j]]?a[j]:b[j];
			flag = 1;
			if(!(check1(t[i].first,t[i].second,f,s))){
				flag = 0;
			}
			if((flag and dict(a[j],b[j])-dict(t[i].first,t[i].second)<=length) or (dict(a[j],b[j])<=length)){
				cnt++;
			}
		}
		
		if(cnt==m) return 1;
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i<n;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		g[x].push_back(make_pair(y,z));
		g[y].push_back(make_pair(x,z));
		t[i] = make_pair(x,y);
	}
	for(int i = 1;i<=m;i++){
		scanf("%d%d",&a[i],&b[i]);
	}
	int l = 1;int r = maxn*1000;
	int ans = 0;
	dfs(1,0);
	while(l<r){
		int mid = l+r>>1;
		if(check(mid)){
			ans = mid;
			r = mid;
		}
		else{
			l = mid+1;
		}
	}
	
	cout<<ans;
	return 0;
}

这个算法个人计算复杂度应该是$O(nm\log m\log val)$

思路就是暴力修边并且计算该边是否在树上路径上然后二分答案

val即为$\log m*1000$

期望得分应为50pts

真实得分为20pts :详情如下

求解析