记录编号	445708	评测结果	AAAAAAAAAAAAAAAAAAAT
题目名称	[NOIP 2015]运输计划	最终得分	95
用户昵称	CSU_Turkey	是否通过	未通过
代码语言	C++	运行时间	1.831 s
提交时间	2017-09-06 17:24:57	内存使用	22.06 MiB

#include<bits/stdc++.h>
using namespace std;
const int inf=300005;
int n,m,fi[inf],tot,dis[inf],fa[inf],son[inf],size[inf],dep[inf],top[inf],ans,l,r,cnt[inf],big[inf];
struct edge{
	int to,next,cost;
}e[inf*2];
struct ghb{
	int from,to,cost,lc;
}w[inf];
int read(){
	int a=0;
	char ch=getchar();
	while(!(ch<='9'&&ch>='0'))ch=getchar();
	while(ch<='9'&&ch>='0'){
		a=(a<<1)+(a<<3)+('0'^ch);
		ch=getchar();
	}
	return a;
}
void edge_add(int x,int y,int z){
	e[++tot].to=y;
	e[tot].next=fi[x];
	fi[x]=tot;
	e[tot].cost=z;
}
void dfs1(int x){
	for(int i=fi[x];i;i=e[i].next){
		int v=e[i].to;
		if(dep[v])continue;
		dep[v]=dep[x]+1;
		fa[v]=x;
		dis[v]=dis[x]+e[i].cost;
		dfs1(v);
		size[x]+=size[v];
		if(size[v]>size[son[x]])son[x]=v;
	}
}
void dfs2(int x,int y){
	top[x]=y;
	if(son[x])dfs2(son[x],y);
	for(int i=fi[x];i;i=e[i].next){
		int v=e[i].to;
		if(top[v])continue;
		dfs2(v,v);
	}
}
int get_lc(int x,int y){
	while(top[x]!=top[y]){
		if(dep[fa[top[x]]]<dep[fa[top[y]]])swap(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
void dfs3(int x){
	for(int i=fi[x];i;i=e[i].next){
		int v=e[i].to;
		if(v==fa[x])continue;
		dfs3(v);
		big[x]+=big[v];
		cnt[i]=big[v];
	}
}
bool check(int x){
	memset(big,0,sizeof(big));
	int cnt2=0,ma1=-0x3fffffff,ma2=-0x3fffffff;
	for(int i=1;i<=tot;i++){
		if(w[i].cost>x){
			big[w[i].from]++,big[w[i].to]++,big[w[i].lc]-=2,cnt2++;
			ma1=max(ma1,w[i].cost);
		}
	}
	dfs3(1);
	for(int i=1;i<2*n;i++){
		if(cnt[i]==cnt2){
			ma2=max(ma2,e[i].cost);
		}
	}
	return ma1-ma2<=x?0:1;
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int a,b,t;
		a=read(),b=read(),t=read();
		edge_add(a,b,t);
		edge_add(b,a,t);
	}
	for(int i=1;i<=n;i++)size[i]=1;
	tot=0;
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=m;i++){
		int u,v;
		u=read(),v=read();
		w[++tot].lc=get_lc(u,v);
		w[tot].from=u;
		w[tot].to=v;
		w[tot].cost=dis[u]+dis[v]-dis[w[tot].lc]*2;
		r=max(r,w[tot].cost);
	}
	while(l!=r){
		int mid=(l+r)>>1;
		if(check(mid))l=mid+1;
		else r=mid;
	}
	cout<<l;
	return 0;
}