求助P2680

#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,v;
};
int n,m,qx[300010],qy[300010];
long long f1[300010][31],f2[300010][31],d[300010],mds[300010],ds[300010];
long long dep[300010],eg[300010],mxl;
vector<node> mp[300010];
void dfs(int u,int fa,bool f){
	for (int i=0;i<mp[u].size();++i){
		int v=mp[u][i].to;
		if (v==fa){
			continue;
		}
		if (!f){
			dep[v]=dep[u]+1;
			f1[v][0]=u;
			f2[v][0]=mp[u][i].v;
		}
		dfs(v,u,f);
		if (f){
			d[u]+=d[v];
			eg[u]=d[v];
		}
	}
}//1:树上差分 0:lca初始化 
long long lca(int x,int y,bool f){
	if (dep[x]<dep[y]){
		swap(x,y);
	}
	long long res=0;
	for (int i=30;i>=0;--i){
		if (dep[f1[x][i]]>=dep[y]){
			res+=f2[x][i];
			x=f1[x][i];
		}
	}
	if (x==y){
		return f?res:x;
	}
	for (int i=30;i>=0;--i){
		if (dep[f1[x][i]]!=dep[f1[y][i]]){
			res+=f2[x][i]+f2[y][i];
			x=f1[x][i];y=f1[y][i];
		}
	}
	res+=f2[x][0]+f2[y][0];
	return f?res:f1[x][0];
}//1:求路径权和 0:求lca 
int main(){
	cin>>n>>m;
	long long zz=-1;
	for (int i=1;i<n;++i){
		long long x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		mp[x].push_back({y,z});
		mp[y].push_back({x,z});
		zz=max(zz,z);
		mds[i]=z;
	}
	dep[1]=1;
	dfs(1,0,0);
	for (int j=1;j<=30;++j){
		for (int i=1;i<=n;++i){
			f1[i][j]=f1[f1[i][j-1]][j-1];
			f2[i][j]=f2[f1[i][j-1]][j-1]+f2[i][j-1];
		}
	}
	long long l=0,r=1e9,ans=1e9;
	for (int i=1;i<=m;++i){
		scanf("%d%d",&qx[i],&qy[i]); 
		ds[i]=lca(qx[i],qy[i],1);
		l=max(l,ds[i]);
	}
	mxl=l;
	l=zz;
	while (l<=r){
		long long mid=(l+r)/2;
		int ft=0;
		memset(d,0,sizeof d);
		memset(eg,0,sizeof eg);
		for (int i=1;i<=m;++i){
			if (ds[i]>mid){
				d[qx[i]]+=1;d[qy[i]]+=1;d[lca(qx[i],qy[i],0)]-=2;
				ft+=1;
			}
		}
		dfs(1,0,1);
		long long mx=-1;
		for (int i=1;i<=n;++i){
			if (eg[i]==ft){
				mx=max(mx,mds[i]);
			}
		}
		if (!ft || mxl-mx<=mid){
			ans=min(ans,mid);
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<ans<<endl;
	return 0;
}