记录编号	414832	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	1.474 s
提交时间	2017-06-15 09:39:23	内存使用	28.92 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,x,y,z,maxn,num;
int adj[300001],fr[300001],to[300001];
int dis[300001];
struct kk{
	int s,t,w,next;
}k[600001];
int read(){
	int sum=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum;
}
int swap(int &x,int &y){
	x^=y;
	y^=x;
	x^=y;
}
void init(int s,int t,int w){
	k[num].s=s;
	k[num].t=t;
	k[num].w=w;
	k[num].next=adj[s];
	adj[s]=num++;
}
int fa[300001],son[300001],size[300001],dp[300001];
int v[300001];
void Dfs1(int x){
	son[x]=0;size[x]=1;
	for(int i=adj[x];i!=-1;i=k[i].next){
		int o=k[i].t,w=k[i].w;
		if(o!=fa[x]){
			dp[o]=dp[x]+1;
			fa[o]=x;v[o]=w;
			Dfs1(o);
			size[x]+=size[o];
			if(size[son[x]]<size[o])
				son[x]=o;
		}
	}
}
int top[300001],id[300001],pos[300001],cnt;
void Dfs2(int u,int tp){
	top[u]=tp;id[u]=++cnt;
	pos[cnt]=u;
	if(son[u])
		Dfs2(son[u],tp);
	for(int i=adj[u];i!=-1;i=k[i].next){
		int o=k[i].t;
		if(o!=son[u]&&o!=fa[u])
			Dfs2(o,o);
	}
}
int sum[1200001];
void pushup(int x){
	sum[x]=sum[x<<1]+sum[x<<1|1];
}
void build(int l,int r,int x){
	if(l==r){
		sum[x]=v[pos[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	pushup(x);
}
int query(int s,int t,int l,int r,int x){
	if(s<=l&&r<=t) 
		return sum[x];
	int mid=(l+r)>>1,res=0;
	if(s<=mid)
		res+=query(s,t,l,mid,x<<1);
	if(t>mid)
		res+=query(s,t,mid+1,r,x<<1|1);
	return res;
}
int ask(int x,int y){
	int fx=top[x],fy=top[y];
	int res=0; 
	while(fx^fy){
		if(dp[fx]<dp[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		res+=query(id[fx],id[x],1,n,1);
		x=fa[fx];fx=top[x];
	}
	if(dp[x]>dp[y])
		swap(x,y);
	if(id[x]<id[y])
		res+=query(id[x]+1,id[y],1,n,1);
	return res;
}
int cha[300001];
void S(int x,int y){
	cha[x]++;
	cha[y+1]--;
	return;
}
void C(int x,int y){
	int fx=top[x],fy=top[y];
	while(fx^fy){
		if(dp[fx]<dp[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		S(id[fx],id[x]);
		x=fa[fx];fx=top[x];
	}
	if(dp[x]<dp[y])
		swap(x,y);
	S(id[son[y]],id[x]);
}
bool judge(int diss){
	memset(cha,0,sizeof(cha));
	int s=0;
	for(int i=1;i<=m;++i)
		if(dis[i]>diss){
			s++;
			C(fr[i],to[i]);
		}
	if(!s)
		return true;
	for(int i=1;i<=n;++i)
		cha[i]+=cha[i-1];
	for(int i=2;i<=n;++i)
		if(cha[id[i]]==s&&maxn-v[i]<=diss)
			return true;
	return false;
	
}
int erfen(int l,int r){
	if(l==r)
		return r; 
	int mid=(l+r)>>1;
	if(judge(mid))
		return erfen(l,mid);
	else 
		return erfen(mid+1,r);
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	memset(adj,-1,sizeof(adj));
	n=read();m=read();
	for(int i=1;i<n;++i){
		x=read();y=read();z=read();
		init(x,y,z);
		init(y,x,z);
	}
	Dfs1(1);Dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=m;++i){
		fr[i]=read();
		to[i]=read();
		dis[i]=ask(fr[i],to[i]);
		if(dis[i]>maxn)
			maxn=dis[i];
	}
	printf("%d",erfen(0,maxn));
	 //while(1);
	return 0;
}