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

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

int n,m,f[300010][20],dis[300010],dep[300010],l,r,mid,jd[300010],h[300010],cnt,tot,mxe;

struct edges
{
	int from,to,weight,nxt;
}e[600010];

void addedges(int from,int to,int weight)
{
	cnt++;
	e[cnt].from=from;
	e[cnt].to=to;
	e[cnt].weight=weight;
	e[cnt].nxt=h[from];
	h[from]=cnt;
}

struct plans
{
	int s,t,lca,weight;
}p[300010];

void dfs(int u)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		if(!dep[e[i].to])
		{
			dep[e[i].to]=dep[u]+1;
			f[e[i].to][0]=u;
			dis[e[i].to]=dis[u]+e[i].weight;
			dfs(e[i].to);
		}
	}
	return;
}

void initt()
{
	for(int i=1;i<=19;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
}

int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	int d=dep[x]-dep[y];
	for(int i=0;d;d>>=1,i++)
	{
		if(d&1)
		{
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=17;i>=0;i--)
	{
		if(f[x][i]!=f[y][i]&&f[x][i]!=0)
		{
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

int dfsjd(int u)
{
	for(int i=h[u];i;i=e[i].nxt)
	{
		if(dep[e[i].to]>dep[u])
		{
			jd[u]+=dfsjd(e[i].to);
		}
	}//cout<<u<<" "<<jd[u]<<endl;
	if(jd[u]==tot) mxe=max(mxe,dis[u]-dis[f[u][0]]);
	return jd[u];
}

bool check(int d)
{
	int mx=0;
	mxe=0;
	tot=0;
	memset(jd,0,sizeof(jd));
	for(int i=1;i<=m;i++)
	{
		if(p[i].weight>d)
		{
			mx=max(mx,p[i].weight);
			tot++;
			jd[p[i].s]++;
			jd[p[i].t]++;
			jd[p[i].lca]-=2;
		}
	}
	dfsjd(1);//cout<<mxe<<endl;
	if(mx-mxe>d) return 0;
	return 1;
}

int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		addedges(a,b,c);
		addedges(b,a,c);
	}
	dep[1]=1;
	dfs(1);
	initt();
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&p[i].s,&p[i].t);
		p[i].lca=lca(p[i].s,p[i].t);
		p[i].weight=dis[p[i].s]+dis[p[i].t]-2*dis[p[i].lca];
		r=max(r,p[i].weight);
	}
	while(l!=r)
	{
		mid=(l+r)/2;//cout<<l<<" "<<r<<" "<<mid<<endl;
		if(check(mid))
		{
			r=mid;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<l;
	return 0;
}