记录编号	469583	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	1.701 s
提交时间	2017-11-03 15:23:28	内存使用	20.92 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 300005
struct node
{
	int x,y,lca,dis;
	inline node(){}
	inline node(int _x,int _y,int _lca,int _dis):x(_x),y(_y),lca(_lca),dis(_dis){}
	inline bool operator <(const node &o)const{return dis>o.dis;}
}a[N];
int head[N],nxt[N<<1],to[N<<1],d[N<<1];
int size[N],son[N],f[N],deep[N],dis[N],top[N],s[N];
int n,m,x,y,z,lca,tmp,l,r,mid,tot,num;
inline void add(int x,int y,int z)
{
	nxt[++num]=head[x],to[num]=y,d[num]=z,head[x]=num;
	nxt[++num]=head[y],to[num]=x,d[num]=z,head[y]=num;
}
void dfs(int now,int fa,int depth,int dist)
{
	f[now]=fa,deep[now]=depth;
	size[now]=1,dis[now]=dist;
	int tmp=0;
	for(int i=head[now];i;i=nxt[i])
	  if(to[i]!=fa)
	  {
		dfs(to[i],now,depth+1,dist+d[i]);
		size[now]+=size[to[i]];
		if(size[to[i]]>tmp) tmp=size[to[i]],son[now]=to[i];
	  }
}
void dfs2(int now,int high)
{
	top[now]=high;
	if(son[now]) dfs2(son[now],high);
	for(int i=head[now];i;i=nxt[i])
	  if(to[i]!=f[now]&&to[i]!=son[now]) dfs2(to[i],to[i]);
}
inline int LCA(int x,int y)
{
	while(top[x]!=top[y])
	  if(deep[top[x]]>deep[top[y]]) x=f[top[x]];
	  else y=f[top[y]];
	return deep[x]<deep[y]?x:y;
}
int solve(int now,int fa)
{
	for(int i=head[now];i;i=nxt[i])
	  if(to[i]!=fa) s[now]+=solve(to[i],now);
	if(s[now]==tot) tmp=max(tmp,dis[now]-dis[f[now]]);
	int ans=s[now];s[now]=0;
	return ans;
}
inline bool check(int mid)
{
	tmp=tot=0;
	for(int i=1;i<=m;i++)
	  if(a[i].dis>mid) tot=i,s[a[i].x]++,s[a[i].y]++,s[a[i].lca]-=2;
	  else break;
	solve(1,0);
	if(a[1].dis-tmp<=mid) return 1;
	return 0;
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	  scanf("%d%d%d",&x,&y,&z),add(x,y,z);
	dfs(1,0,1,0),dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		lca=LCA(x,y),tmp=dis[x]+dis[y]-(dis[lca]<<1);
		a[i]=node(x,y,lca,tmp),r=max(r,tmp);
	}
	sort(a+1,a+m+1);
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d",l);
	return 0;
}