记录编号	348237	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	1.132 s
提交时间	2016-11-13 23:57:12	内存使用	20.68 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define maxn 300100
struct Node{
	int to,next,dis;
}edge[maxn<<1];
int head[maxn],tot;
void Addedge(int x,int y,int w){
	edge[++tot].to=y;
	edge[tot].next=head[x];
	edge[tot].dis=w;
	head[x]=tot;
} 
inline void QR(int& x){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),'0'<=ch&&ch<='9')x=x*10+ch-48;
}
int size[maxn],fa[maxn],top[maxn],son[maxn],deep[maxn],cnt,dfn[maxn],dis[maxn],maxnum[maxn],sumnum[maxn],num[maxn],dist[maxn];
int from[maxn],to[maxn],value[maxn];
int n,m,x,y,z,l,r,mid,temp;
int ans;
void dfs1(int x){
	size[x]=1;
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!size[p]){
			fa[p]=x;
			deep[p]=deep[x]+1;
			dis[p]=edge[i].dis+dis[x];
			dist[p]=edge[i].dis;
			dfs1(p);
			size[x]+=size[p];
			if(size[p]>size[son[x]])son[x]=p;
		}
	}
}
void dfs2(int x,int tp){
	top[x]=tp,dfn[x]=++cnt;
	if(son[x])dfs2(son[x],tp);
	for(int i=head[x];i;i=edge[i].next){
		int p=edge[i].to;
		if(!dfn[p])dfs2(p,p);
	}
}
int lca(int x,int y){
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])return y;
	else return x;
}
void update(int x,int y)
{
	while(top[x]!=top[y]){
		if(deep[top[x]]<deep[top[y]])swap(x,y);
		if(dfn[top[x]]<=dfn[x])num[dfn[top[x]]]++,num[dfn[x]+1]--;
		x=fa[top[x]];
	}
	if(deep[x]>deep[y])swap(x,y);
	if(dfn[son[x]]<=dfn[y])num[dfn[son[x]]]++,num[dfn[y]+1]--;
}
bool Check(int mid)
{
	memset(num,0,sizeof num);
	int cnt=0;
	for(int i=1;i<=m;i++)
	{
		if(value[i]>mid){
			cnt++;
			update(from[i],to[i]);
		}
	}
	if(!cnt)return 1;
	for(int i=1;i<=n;i++)num[i]+=num[i-1];
	for(int i=2;i<=n;i++){if(num[dfn[i]]==cnt)
		if( temp-dist[i]<=mid)return 1;
	}
	return 0;
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	QR(n),QR(m);
	for(int i=1;i<n;i++){
		QR(x),QR(y),QR(z);
		Addedge(x,y,z),Addedge(y,x,z);
	}
	deep[1]=1;
	dfs1(1),dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		QR(from[i]),QR(to[i]);
		value[i]=dis[from[i]]+dis[to[i]]-2*dis[lca(from[i],to[i])];
		r=max(r,value[i]);
	}
	l=0,temp=r;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(Check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	printf("%d\n",ans);
	return 0;
}