Luogu P2680

#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 300010
#define maxlog 20
using namespace std;

int n,m,cnt,ans,sum,dfs_clock=0;
int head[M<<1],fr[M],to[M],mem[M],dfn[M],dis[M],dep[M];
int fa[M][maxlog+10];
bool vis[M];
struct edge{
	int to,nxt,w;
}e[M<<1];
struct Node{
	int u,v,dis,lca;
}node[M<<1];

int tmp[M];
bool Judge(int lim){
	int tot=0,num=0;
	memset(tmp,0,sizeof(tmp));
	for(int i=1;i<=m;i++)
		if(node[i].dis>lim){
			tmp[node[i].u]+=1;
			tmp[node[i].v]+=1;
			tmp[node[i].lca]-=2;
			num=max(num,node[i].dis-lim);
			tot++;
		}
	if(!tot) return true;
	for(int i=n;i>=1;i--) tmp[fa[dfn[i]][0]]+=tmp[dfn[i]];
	for(int i=2;i<=n;i++)
		if((tmp[i]==tot)&&(dis[i]-dis[fa[i][0]]>=num))
			return true;
	return false;
}

void Add(int x,int y,int z){
	cnt++;
	e[cnt].to=y;
	e[cnt].nxt=head[x];
	e[cnt].w=z;
	head[x]=cnt;
}

void Dfs(int u,int f,int d){
	vis[u]=1;
	dfn[++dfs_clock]=u;
	fa[u][0]=f;
	dep[u]=d;
	for(int i=1;i<=maxlog-1;i++)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(vis[v]) continue;
		dis[v]=dis[u]+e[i].w;
		Dfs(v,u,d+1); 
	}
}

int Lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	int d=dep[x]-dep[y];
	for(int i=maxlog;i>=0;i--)
		if((1<<i)&d) x=fa[x][i];
	if(x==y) return x;
	for(int i=maxlog;i>=0;i--)
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		Add(a,b,c);
		Add(b,a,c);
		sum+=c;
	}
	Dfs(1,0,1);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&node[i].u,&node[i].v);
		node[i].lca=Lca(node[i].u,node[i].v);
		node[i].dis=dis[node[i].u]+dis[node[i].v]-2*dis[node[i].lca];
	}
	int l=0,r=sum+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Judge(mid))
			ans=mid,r=mid-1;
		else l=mid+1;
	}	
	printf("%d\n",ans);
	return 0;
}