记录编号	330166	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.911 s
提交时间	2016-10-26 07:24:51	内存使用	22.13 MiB

#include <queue>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
#define ll long long 
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
	return x*f;
}
const int maxn=301000;
struct edge{
	int to,next,dis;
}e[maxn*2];
int tot,head[maxn];
void add(int u,int v,int w){
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].next=head[u];
	head[u]=tot;
}
int n,m,hl[maxn],hr[maxn],dist[maxn];
int size[maxn],fa[maxn],deep[maxn];
int dis[maxn],top[maxn],son[maxn];
int max_d,d[maxn],mark[maxn],dfs_cnt,dfn[maxn];
void dfs(int u){
	size[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(size[to])continue;
		fa[to]=u;
		deep[to]=deep[u]+1;
		dis[to]=dis[u]+e[i].dis;
		d[to]=e[i].dis;
		dfs(to);
		size[u]+=size[to];
		if(size[to]>size[son[u]]) son[u]=to;
	}
}
void dfs(int u,int tp){
	dfn[u]=++dfs_cnt,top[u]=tp;
	if(son[u])dfs(son[u],tp);
	for(int i=head[u];i;i=e[i].next){
		int to=e[i].to;
		if(!top[to])dfs(to,to);
	}
}
int lca(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]])swap(a,b);
		a=fa[top[a]];
	}
	return deep[a]<deep[b]?a:b;
}
void Mark(int l,int r){
	if(l>r)return;
	mark[l]++,mark[r+1]--;
}
void set(int a,int b){
	while(top[a]!=top[b]){
		if(deep[top[a]]<deep[top[b]])swap(a,b);
		Mark(dfn[top[a]],dfn[a]);
		a=fa[top[a]];
	}
	if(deep[a]<deep[b])swap(a,b);
	Mark(dfn[son[b]],dfn[a]);
}
bool check(int x){
	memset(mark,0,sizeof mark);
	int cnt=0;
	for(int i=1;i<=m;i++)if(dist[i]>x)cnt++,set(hl[i],hr[i]);
	if(!cnt)return 1;
	for(int i=1;i<=n;i++)mark[i]+=mark[i-1];
	for(int i=2;i<=n;i++)
		if(mark[dfn[i]]==cnt&&max_d-d[i]<=x)return 1;
	return 0;
}

int main(){
	freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int a=read(),b=read(),c=read();
		add(a,b,c);add(b,a,c);
	}
	dfs(1);dfs(1,1);
	//printf("ok\n");
	int l=0,r=0;
	for(int i=1;i<=m;i++){
		hl[i]=read(),hr[i]=read(),
		dist[i]=dis[hl[i]]+dis[hr[i]]-2*dis[lca(hl[i],hr[i])];
		r=max(r,dist[i]);
		max_d=r;
	}
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid))r=mid-1;
		else l=mid+1;
	}
	if(check(r))printf("%d\n",r);
	else printf("%d\n",l);	
	fclose(stdin);fclose(stdout);
	return 0;
}