RT,求助大佬帮忙捉虫

//By: Luogu@wangdemao(308854)
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long

using namespace std;

const int INF=0x3f3f3f3f;

int diff[500010],ans[500010],Max=-INF;

struct Edge
{
	int v,w;
};
vector<Edge> adj[500010];

struct Job
{
	int u,v,lca,l;
	
	bool operator<(const Job &a) const
	{
		return l>a.l;
	}
}jobs[500010];

int father[500010][100];
int depth[500010];
int dis[500010];
int weight[500010];
int n,m;

void lca_init(int u,int f,int w)
{
	father[u][0]=f;
	depth[u]=depth[f]+1;
	dis[u]=dis[f]+w;
	weight[u]=w;
	
	for(int i=1;i<=28;i++)
		father[u][i]=father[father[u][i-1]][i-1];
		
	for(int i=0;i<adj[u].size();i++)
		if(adj[u][i].v!=f)
			lca_init(adj[u][i].v,u,adj[u][i].w);
	
	return ;
}

int lca(int a,int b)
{
	if(depth[b]>depth[a])
		swap(a,b);
	
	while(depth[b]!=depth[a])
		a=father[a][(int)log2(depth[a]-depth[b])];
		
	if(a==b)
		return a;
		
	for(int i=log2(depth[a]);i>=0;i--)
		if(father[a][i]!=father[b][i])
			a=father[a][i],b=father[b][i];
	
	if(father[a][0]!=father[b][0])
		exit(1);
	
	return father[a][0];
}

void dfs(int u,int bigger)
{
	ans[u]+=diff[u];
	
	for(int i=0;i<adj[u].size();i++)
		if(adj[u][i].v!=father[u][0])
		{
			dfs(adj[u][i].v,bigger);
			
			ans[u]+=ans[adj[u][i].v];
		}
		
	if(ans[u]>=bigger)
		Max=max(Max,weight[u]);
	
	return ;
}

bool judge(int mid)
{
	memset(diff,0,sizeof(diff));
	memset(ans,0,sizeof(ans));
	Max=0;
	
	int bigger=0;
	
	for(int i=1;i<=m;i++)
	{
		if(jobs[i].l>mid)
			diff[jobs[i].u]++,diff[jobs[i].v]++,diff[jobs[i].lca]-=2;
		
		if(jobs[i].l>mid)
			bigger++;
	}
	
	dfs(1,bigger);
	
	if(mid==3)
	{
		cout<<Max<<endl;
	}

	return jobs[1].l-Max<=mid;
}

int main()
{
	//freopen("C:\\Users\\wdm\\Downloads\\P2680_1.in","w",stdin);
	
	cin>>n>>m;
	
	for(int i=1;i<=n-1;i++)
	{
		int x,y,w;
		
		cin>>x>>y>>w;
		
		adj[x].push_back({y,w});
		adj[y].push_back({x,w});
	}
	
	lca_init(1,0,0);
	
	for(int i=1;i<=m;i++)
	{
		int u,v;
		
		cin>>u>>v;
		
		jobs[i].u=u;
		jobs[i].v=v;
		jobs[i].lca=lca(u,v);
		jobs[i].l=dis[u]+dis[v]-2*dis[lca(u,v)];
	}
	
	sort(jobs+1,jobs+1+m);
	cout<<judge(3);
	
	int l=0,r=1e9;
	int ans=10000;
	
	while(l+2<=r)
	{
		int mid=(l+r)>>1;
		
		//cout<<l<<" "<<r<<" "<<mid<<endl;
		
		if(judge(mid))
			ans=mid,r=mid-1;
		else
			l=mid+1;
	}
	
	for(int i=min(r+5,jobs[1].l);i>=min(l-5,0);i--)
		if(judge(i))
		{
			cout<<i;
			
			return 0;
		}
	
	return 0;
}