记录编号	206978	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	~Love Star	是否通过	通过
代码语言	C++	运行时间	1.761 s
提交时间	2015-11-10 07:18:43	内存使用	34.64 MiB

#include<set>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300005;
int n,m;
set<int> s1;
set<int> s2;
set<int>::iterator It;
vector<int> G[maxn];
struct Edge{
	int from,to,cap;
};
struct Heapnode{
	int id,len;
};
bool operator <(const Heapnode &a,const Heapnode &b)
{
	return a.len<b.len;
}
bool operator >(const Heapnode &a,const Heapnode &b)
{
	return a.len>b.len;
}
priority_queue<Heapnode> heap;
struct Query{
	int u,v,len,lca;
	bool operator < (const Query& rhs) const
	{
		return len>rhs.len;
	}
};
Query Q[maxn];
vector<Edge> edges;
int f[maxn][20],dist[maxn],d[maxn],num[maxn];
int readint()
{
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
void dfs(int u,int fa,int sum)
{
	dist[u]=sum;
	d[u]=d[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<20;i++)
	f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<G[u].size();i++)
	{
		if(edges[G[u][i]].to!=fa) dfs(edges[G[u][i]].to,u,sum+edges[G[u][i]].cap);
		else num[u]=G[u][i];
	}
}
void Lca1(int &u,int &v,int cnt)
{
	int su=u,sv=v;
	if(d[u]>d[v])
	{
		u^=v;
		v^=u;
		u^=v;
	}
	int dis=d[v]-d[u];
	int ret=dist[v]+dist[u];
	for(int i=19;i>=0;i--)
	{
		if((dis>>i)&1) v=f[v][i];
	}
	for(int i=19;i>=0;i--)
	{
		if(f[u][i]!=f[v][i])
		{
			u=f[u][i];
			v=f[v][i];
		}
	}
	if(u!=v)
	{
		u=f[u][0];
		v=f[v][0];
	}
	ret-=2*dist[u];
	Q[cnt].u=su;
	Q[cnt].v=sv;
	Q[cnt].len=ret;
	Q[cnt].lca=u;
}
void Add_Edge1(int u,int k)
{
	if(u==Q[k].lca) return;
	s1.insert(num[u]);
	heap.push((Heapnode){num[u],edges[num[u]].cap});
	Add_Edge1(edges[num[u]].to,k);
}
void Add_Edge(int u,int k)
{
	if(u==Q[k].lca) return;
	s2.insert(num[u]);
	Add_Edge(edges[num[u]].to,k);
}
int main()
{
	freopen("transport.in","r",stdin);
	freopen("transport.out","w",stdout);
	n=readint();m=readint();
	int from,to,cap;
	for(int i=1;i<n;i++)
	{
		from=readint();to=readint();cap=readint();
		edges.push_back((Edge){from,to,cap});
		edges.push_back((Edge){to,from,cap});
		G[from].push_back(edges.size()-2);
		G[to].push_back(edges.size()-1);
	}
	dfs(1,0,0);
	int u,v,len;
	for(int i=0;i<m;i++)
	{
		u=readint();v=readint();
		Lca1(u,v,i);
	}
	sort(Q,Q+m);
	int ans=0;
	s1.clear();
	s2.clear();
	Add_Edge1(Q[0].u,0);
	Add_Edge1(Q[0].v,0);
	ans=Q[0].len-(heap.top()).len;
	for(int i=1;i<m;i++)
	{
		if(ans>=Q[i].len) break;
		ans=Q[i].len;
		Add_Edge(Q[i].u,i);
		Add_Edge(Q[i].v,i);
		It=s1.begin();
		for(It;It!=s1.end();)
		{
			int cnt=(*It);
			It++;
			if(!s2.count(cnt))
			{
				s1.erase(cnt);
			}
		}
		s2.clear();
		if(s1.empty()) break;
		while(!s1.count(heap.top().id))
		{
			heap.pop();
		}
		if(Q[0].len-(heap.top()).len>=ans) break;
		ans=Q[0].len-(heap.top()).len;
	}
	printf("%d",ans);
	return 0;
}