记录编号	441996	评测结果	AAAAAAAAAAAAAAAAAAAT
题目名称	[NOIP 2015]运输计划	最终得分	95
用户昵称	CSU_Turkey	是否通过	未通过
代码语言	C++	运行时间	2.225 s
提交时间	2017-08-26 07:43:05	内存使用	47.23 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,head[300005],h,dep[300005],dis[300005],lc[300005][25],t,a[300005],f[600005];
struct edge{
	int to,next,cost;
}e[600005];
struct d{
	int from,to,cost,lc;
}q[300005];
void edge_add(int x,int y,int z){
	e[++h].to=y;
	e[h].cost=z;
	e[h].next=head[x];
	head[x]=h;
	e[++h].to=x;
	e[h].cost=z;
	e[h].next=head[y];
	head[y]=h;
}
void dfs(int x){
	for(int i=head[x];i;i=e[i].next){
		if(!dep[e[i].to]){
			dep[e[i].to]=dep[x]+1;
			dis[e[i].to]=dis[x]+e[i].cost;
			lc[e[i].to][0]=x;
			dfs(e[i].to);
		}
	}
}
void init_lca(){
	dep[1]=1;
	dfs(1);
	for(int i=1;(1<<i)<=n;i++){
		for(int j=1;j<=n;j++){
			lc[j][i]=lc[lc[j][i-1]][i-1];
		}
	}
}
int q_lc(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	int o=dep[x]-dep[y];
	for(int i=0;i<=24;i++){
		if(o&(1<<i)){
			x=lc[x][i];
			o-=(1<<i);
		}
	}
	for(int i=24;i>=0;i--){
		if(lc[x][i]!=lc[y][i]){
			x=lc[x][i];
			y=lc[y][i];
		}
	}
	if(x==y){
		return x;
	}
	else{
		return lc[x][0];
	}
}
void dfs2(int x){
	for(int i=head[x];i;i=e[i].next){
		if(dep[e[i].to]<dep[x])continue;
		dfs2(e[i].to);
		a[x]+=a[e[i].to];
		f[i]=a[e[i].to];
	}
}
bool check(int x){
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	int ans=0,maa=-1;;
	for(int i=1;i<=t;i++){
		if(q[i].cost>x){
			a[q[i].from]++;
			a[q[i].to]++;
			a[q[i].lc]-=2;
			ans++;
			maa=max(maa,q[i].cost);
		}
	}
	if(maa==-1){
		return 0;
	}
/*	for(int i=1;i<=6;i++)
	cout<<a[i]<<" ";
*/	dfs2(1);
	int ma=-1;
	for(int i=1;i<2*n;i++){
		if(f[i]==ans){
			ma=max(ma,e[i].cost);
		}//cout<<f[i]<<" "<<e[i].to<<endl;
	}
/*	for(int i=1;i<2*n;i++)
	cout<<f[i]<<" ";*/
//	cout<<endl;
	//cout<<ans<<endl;
//	cout<<maa<<" "<<ma<<endl;
	if(maa-ma>x){
		return 1;
	}
	else{
		return 0;
	}
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		edge_add(x,y,z);
	}
	init_lca();
	int r=1;
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		q[++t].from=x;
		q[t].to=y;
		q[t].lc=q_lc(x,y);
		q[t].cost=dis[x]+dis[y]-2*dis[q[t].lc];
		r=max(q[t].cost,r);
	}
	int l=1;
	while(l!=r){//cout<<l<<" "<<r<<endl;
		int mid=(l+r)>>1;
		if(check(mid)){
			l=mid+1;
		}
		else{
			r=mid;
		}
	}
	cout<<l;
	return 0;
}