记录编号	222949	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.884 s
提交时间	2016-02-05 22:01:34	内存使用	22.32 MiB

#define MAXN 300010UL
#define MAXS 21UL
 
#include <stdio.h>
#include <string.h>
 
struct Edge{int v,w,nx;};
Edge edge[MAXN<<1];
int n,m,ec,mark[MAXN],headlist[MAXN],tree_size[MAXN],fa[MAXN],depth[MAXN],op1[MAXN],op2[MAXN],temp_ans[MAXN],max_e,dis[MAXN],Ans,top[MAXN],son[MAXN],w[MAXN],cnt,edge_w[MAXN];
bool vist[MAXN];
 
inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}
 
inline void Add_Edge(int u,int v,int w){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	edge[ec].w=w;
	headlist[u]=ec;
	return;
}
 
void dfs(int p){
	vist[p]=true;
	tree_size[p]=1;
	for(int i=headlist[p];i;i=edge[i].nx){
		if(vist[edge[i].v]) continue;
		fa[edge[i].v]=p;
		depth[edge[i].v]=depth[p]+1;
		dis[edge[i].v]=dis[p]+edge[i].w;
		edge_w[edge[i].v]=edge[i].w;
		dfs(edge[i].v);
		tree_size[p]+=tree_size[edge[i].v];
		if(tree_size[son[p]]<tree_size[edge[i].v])
			son[p]=edge[i].v;
	}
	return;
}
 
void build_tree(int p,int tp){
	top[p]=tp;
	w[p]=++cnt;
	if(son[p]!=0) build_tree(son[p],tp);
	for(int i=headlist[p];i;i=edge[i].nx)
		if(edge[i].v!=son[p]&&edge[i].v!=fa[p]) build_tree(edge[i].v,edge[i].v);
	return;
}
 
inline void Build(){
	depth[1]=1;
	dfs(1);
	build_tree(1,1);
	return;
}
 
inline int lca(int a,int b){
	while(top[a]!=top[b]){
		if(depth[top[a]]<depth[top[b]]) a^=b,b^=a,a^=b;
		a=fa[top[a]];
	}
	return depth[a]<depth[b]?a:b;
}
 
inline void ReadIn(){
	n=in(),m=in();
	for(int i=1,a,b,t;i<n;i++){
		a=in(),b=in(),t=in();
		Add_Edge(a,b,t),Add_Edge(b,a,t);
	}
	Build();
	for(int i=1;i<=m;i++){
		op1[i]=in(),op2[i]=in();
		temp_ans[i]=dis[op1[i]]+dis[op2[i]]-(dis[lca(op1[i],op2[i])]<<1);
		if(temp_ans[i]>max_e) max_e=temp_ans[i];
	}
	return;
}
 
inline void Set(int l,int r){
	if(l>r) return;
	mark[l]++;
	mark[r+1]--;
	return;
}
 
inline void Mark(int a,int b){
	while(top[a]!=top[b]){
		if(depth[top[a]]<depth[top[b]]) a^=b,b^=a,a^=b;
		Set(w[top[a]],w[a]);
		a=fa[top[a]];
	}
	if(depth[a]>depth[b]) a^=b,b^=a,a^=b;
	Set(w[son[a]],w[b]);
	return;
}
 
inline bool Check(int check_val){
	memset(mark,0,sizeof(mark));
	cnt=0;
	for(int i=1;i<=m;i++)
		if(check_val<temp_ans[i]) cnt++,Mark(op1[i],op2[i]);
	if(!cnt) return true;
	for(int i=2;i<=n;i++) mark[i]+=mark[i-1];
	for(int i=2;i<=n;i++) if(mark[w[i]]==cnt)
		if(max_e-edge_w[i]<=check_val) return true;
	return false;
}
 
inline void Div_2(){
	int l=0,r=max_e,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(Check(mid)) Ans=mid,r=mid-1;
		else l=mid+1;
	}
	return;
}
 
int main(){
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	ReadIn();
	Div_2();
	printf("%d",Ans);
	return 0;
}