记录编号	315118	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	面对疾风吧 疾风 疾风吧	是否通过	通过
代码语言	C++	运行时间	1.579 s
提交时间	2016-10-04 18:54:47	内存使用	23.21 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 300010
using namespace std;
struct Edge{
	int t,next,d;
}e[maxn<<1];int len,head[maxn];
struct Que{
	int x,y,len;
}q[maxn];
int n,m,dis[maxn],cnt,d[maxn],l,r;
int ufs[maxn],pos[maxn],id[maxn],v[maxn],son[maxn],size[maxn],depth[maxn],top[maxn];
void _addedge(int x,int y,int z){
	len++;
	e[len].t=y;
	e[len].d=z;
	e[len].next=head[x];
	head[x]=len;
}
void _dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].t;
		if(ufs[x]==y)continue;
		ufs[y]=x;
		depth[y]=depth[x]+1;
		dis[y]=dis[x]+e[i].d;
		v[y]=e[i].d;
		_dfs1(y);
		size[x]+=size[y];
		if(size[y]>size[ son[x] ])son[x]=y;
	}
}
void _dfs2(int x,int tp){
	top[x]=tp;
	pos[++cnt]=x;
	id[x]=cnt;
	if(son[x])_dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].next){
		int y=e[i].t;
		if(ufs[x]==y||y==son[x])continue;
		_dfs2(y,y);
	}
}
int get_lca(int x,int y){
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(depth[tx]<depth[ty]){swap(x,y);swap(tx,ty);}
		x=ufs[tx];tx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	return x;
}
void _setwork(int l,int r){
	d[l]++;d[r+1]--;
}
void get_set(int x,int y){
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(depth[tx]<depth[ty]){swap(tx,ty);swap(x,y);}
		_setwork(id[tx],id[x]);
		x=ufs[tx];tx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	if(id[x]+1<=id[y])_setwork(id[x]+1,id[y]);
}
bool _check(int mid){
	memset(d,0,sizeof(d));
	int num=0,sum=0,Max=0;
	for(int i=1;i<=m;i++){
		if(q[i].len>mid){
			get_set(q[i].x,q[i].y);
			num++;
			Max=max(Max,q[i].len);
		}		
	}
	if(!num)return 1;
	for(int i=1;i<=n;i++){
		sum+=d[i];
		if(sum>=num){
			int x=v[ pos[i] ];
			if(Max-x<=mid)return 1;
		}
	}
	return 0;
}
int _search(){
	while(l<=r){
		int mid=(l+r)>>1;
		if(_check(mid))r=mid-1;
		else l=mid+1;
	}
	return l;
}
int main(){
	freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		_addedge(x,y,z);_addedge(y,x,z);
	}
	depth[1]=1;
	_dfs1(1);
	_dfs2(1,1);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].x,&q[i].y);
		int rt=get_lca(q[i].x,q[i].y);
		q[i].len=dis[ q[i].x]+dis[ q[i].y ]-2*dis[rt];
		r=max(r,q[i].len);
	}
	printf("%d\n",_search());
	fclose(stdin);fclose(stdout);
}