记录编号	263526	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.025 s
提交时间	2016-05-25 14:20:41	内存使用	30.04 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
//#include"debug.h"
using namespace std;

const int maxl=300010;
struct edge{
	int f,t,l;
}w[maxl*2];
int i,j,now,cnt,num,n,m,head[maxl],tail[maxl],next[maxl*2];
int dfn[maxl],size[maxl],h[maxl],fa[maxl],up[maxl],link[maxl],top[maxl],sum[maxl];
//top[i]表示链i的顶部点，link[i]表示i所在的链 
//up[i]表示i的上向边长，sum[i]表示所在链上up的前缀和 

char ch;int _x;//快速读 
int read(){
	_x=0;ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') _x=_x*10+ch-'0',ch=getchar();
	return _x;
}

//树剖求LCA 
int z[maxl],r;
void bfs(){
	size[1]=fa[1]=h[1]=z[r=1]=1;
	for (i=1;i<=r;i++)
	for (j=head[z[i]];j!=0;j=next[j])
	if (fa[w[j].t]==0){
		fa[w[j].t]=z[i];
		up[w[j].t]=w[j].l;
		h[w[j].t]=h[z[i]]+1;
		z[++r]=w[j].t;
	}
	else{
		swap(w[j],w[head[z[i]]]);
		head[z[i]]=next[head[z[i]]];
	} 
	for (i=n;i>1;i--) size[z[i]]++,size[fa[z[i]]]+=size[z[i]];
}
void change(){
	for (i=1;i<=n;i++)
	for (j=head[i];j!=0;j=next[j])
	if (size[w[j].t]>size[w[head[i]].t])
		swap(w[j],w[head[i]]);
	top[1]=link[1]=cnt=dfn[1]=z[r=1]=1;
	for (i=1;i<=r;i++)
	if (head[z[i]]!=0){
		now=w[head[z[i]]].t;
		sum[now]=up[now]+sum[z[i]];
		dfn[now]=dfn[z[i]]+1;
		link[now]=link[z[i]];
		for (j=head[z[i]];j!=0;j=next[j]) z[++r]=w[j].t;
		for (j=next[head[z[i]]];j!=0;j=next[j]){
			dfn[w[j].t]=dfn[now]+size[now];
			now=w[j].t;
			link[now]=++cnt;top[cnt]=now;sum[now]=up[now];
		}
	}
}
bool check(int x,int y){
	return dfn[y]>=dfn[x]&&dfn[y]<dfn[x]+size[x];
}
bool cmp(int x,int y){
	return dfn[x]>dfn[y];
} 
int ans1,ans2;//ans1表示询问的路径长，ans2表示询问的LCA 
void lca(int x,int y){
	int a=x,b=y;
	ans1=0;
	while (link[a]!=link[b]){
		if (h[top[link[a]]]<h[top[link[b]]]){
			ans1+=sum[b];b=fa[top[link[b]]];
		}
		else ans1+=sum[a],a=fa[top[link[a]]];
	}
	if (h[a]>h[b]) swap(a,b);
	ans2=a;
	ans1+=sum[b]-sum[a];
}

struct line{
	int a,b,lca,len,l,r;
}l[maxl];
int hash[maxl];

bool check(int x){
	int le=1,ri=num,ma=0;
	for (i=1;i<=m;i++)
	if (l[i].len>x){
		le=max(le,l[i].l);
		ri=min(ri,l[i].r);
	}
	if (le>=ri) return 0;
	lca(z[le],z[ri]);
	for (i=z[le];i!=ans2;i=fa[i]) ma=max(ma,up[i]);
	for (i=z[ri];i!=ans2;i=fa[i]) ma=max(ma,up[i]);
	return l[now].len-ma<=x;
}
int erfen(int le,int ri){
	if (le==ri) return le;
	int mid=(le+ri)/2;
	return (check(mid)?erfen(le,mid):erfen(mid+1,ri));
}

int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	n=read();m=read();
	for (i=1;i<n;i++){
		w[i].f=read();w[i].t=read();w[i].l=read();
		w[i+n-1]=w[i];
		swap(w[i+n-1].f,w[i+n-1].t);
		if (head[w[i].f]==0) head[w[i].f]=tail[w[i].f]=i;
			else tail[w[i].f]=next[tail[w[i].f]]=i;
		if (head[w[i].t]==0) head[w[i].t]=tail[w[i].t]=i+n-1;
			else tail[w[i].t]=next[tail[w[i].t]]=i+n-1;
	}
	bfs();change();
	now=0;
	for (i=1;i<=m;i++){
		scanf("%d%d",&l[i].a,&l[i].b);
		lca(l[i].a,l[i].b);
		l[i].len=ans1;l[i].lca=ans2;
		if (l[i].len>l[now].len) now=i;
	}
	
	cnt=0;num=h[l[now].a]+h[l[now].b]-h[l[now].lca]*2+1;
	for (i=l[now].a;i!=l[now].lca;i=fa[i]) hash[i]=++cnt;
	hash[i]=++cnt;cnt=num;
	for (i=l[now].b;i!=l[now].lca;i=fa[i]) hash[i]=cnt--;
	memset(z,0,sizeof z);
	for (i=1;i<=n;i++) if (hash[i]>0) z[hash[i]]=i;
	
	cnt=0;
	int list[10];
	for (i=1;i<=m;i++){
		if (!check(l[i].lca,l[now].a)&&!check(l[i].lca,l[now].b)) goto en;
		if (!check(l[now].lca,l[i].a)&&!check(l[now].lca,l[i].b)) goto en;
		list[++cnt]=l[i].lca;list[++cnt]=l[i].lca;
		list[++cnt]=l[now].lca;list[++cnt]=l[now].lca;
		lca(l[i].a,l[now].a);list[++cnt]=ans2;
		lca(l[i].a,l[now].b);list[++cnt]=ans2;
		lca(l[i].b,l[now].a);list[++cnt]=ans2;
		lca(l[i].b,l[now].b);list[++cnt]=ans2;
		for (j=1;j<=cnt;j++)
			if (cmp(list[j],list[1])) swap(list[1],list[j]);
		for (j=2;j<=cnt;j++)
			if (cmp(list[j],list[2])) swap(list[2],list[j]);
		l[i].l=hash[list[1]];
		l[i].r=hash[list[2]];
		if (l[i].l>l[i].r) swap(l[i].l,l[i].r);
		en:cnt=0;
	}
	
	printf("%d\n",erfen(0,l[now].len));
	return 0;
}