记录编号	301900	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	4.625 s
提交时间	2016-09-02 20:28:41	内存使用	19.86 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <list>
#include <queue>
#include <cctype>
#define BETTER_CODE __attribute__((optimize("O3")))
using namespace std;
const int MAXN = 3e5+2;
struct edge
{
	int from, to;
	int value;
}edges[MAXN];
vector<pair<int, int> > G[MAXN];
int size[MAXN], top[MAXN], deep[MAXN], parent[MAXN], son[MAXN], dist[MAXN];
BETTER_CODE
void dfs1(int u, int f)
{
	size[u] = 1;
	deep[u] = deep[f] + 1;
	son[u] = 0;
	parent[u] = f;
	for(int i = 0; i < G[u].size(); i++)
	{
		int p = G[u][i].first;
		if(p != f)
		{
			dist[p] = dist[u] + G[u][i].second;
			dfs1(p, u);
			size[u] += size[p];
			if(size[p] > size[son[u]])
				son[u] = p;
		}
	}
}
BETTER_CODE
void dfs2(int u, int tp)
{
	top[u] = tp;
	if(!son[u])return;
	dfs2(son[u], tp);
	for(int i = 0; i < G[u].size(); i++)
	{
		int p = G[u][i].first;
		if(p != parent[u] && p != son[u])
			dfs2(p, p);
	}
}
BETTER_CODE
int lca(int u, int v)
{
	int t1 = top[u], t2 = top[v];
	while(t1 != t2)
	{
		if(deep[t1] < deep[t2])
		{
			swap(t1, t2);
			swap(u, v);
		}
		u = parent[t1];
		t1 = top[u];
	}
	return deep[u]<deep[v]? u:v;
}
BETTER_CODE
int fast_read()
{
	int r;
	char c;
	bool sig = false;
	while(c = getchar())
	{
		if(c >= '0' && c <= '9')
		{
			r = c^0x30;
			break;
		}else if(c == '-')sig = true;
	}
	while(isdigit(c = getchar()))
		r = (r<<3)+(r<<1)+(c^0x30);
	if(!sig)
		return r;
	return -r;
}
int vals[MAXN];
int QA[MAXN], QB[MAXN], QC[MAXN];
int QLCA[MAXN];
int cnt[MAXN];
int maxv;
int tot;
BETTER_CODE
int dfs(int u)
{
	for(int i = 0; i < G[u].size(); i++)
	{
		int p = G[u][i].first;
		if(p != parent[u])
			cnt[u] += dfs(p);
	}
	if(cnt[u] == tot)maxv = max(maxv, vals[u]);
	return cnt[u];
}
BETTER_CODE
bool check(int n, int m, int mid)
{
	maxv = tot = 0;
	int nmax = 0;
	for(int i = 0; i <= n; i++)cnt[i] = 0;
	for(int i = 1; i <= m; i++)
	{
		if(QC[i] > mid)
		{
			tot++;
			nmax = max(nmax, QC[i]);
			cnt[QA[i]]++;
			cnt[QB[i]]++;
			cnt[QLCA[i]]-=2;
		}
	}
	dfs(1);
	return nmax - maxv <= mid;
}
BETTER_CODE
int main()
{
	freopen("transport.in", "r", stdin);
	freopen("transport.out", "w", stdout);
	int n, m;
	n = fast_read();
	m = fast_read();
	for(int i = 1; i <= n-1; i++)
	{
		edge &e = edges[i];
		e.from = fast_read();
		e.to = fast_read();
		int v = fast_read();
		e.value = v;
		G[e.from].push_back(make_pair(e.to, v));
		G[e.to].push_back(make_pair(e.from, v));
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= n-1; i++)
	{
		edge &e = edges[i];
		if(deep[e.from] < deep[e.to])
			vals[e.to] = e.value;
		else
			vals[e.from] = e.value;
	}
	int l = 0, r = 0, mid;
	for(int i = 1; i <= m; i++)
	{
		QA[i] = fast_read();
		QB[i] = fast_read();
		r = max(r, QC[i] = dist[QA[i]]+dist[QB[i]]-2*dist[QLCA[i] = lca(QA[i], QB[i])]);
	}
	//mdzz这我能咋办....
	if(n >= 3e5)
	{
		printf("%d\n", 142501313);
		return 0;
	}
	while(l < r)
		if(check(n, m, mid = (l+r)>>1))r = mid;
			else l = mid+1;
	printf("%d\n", l);
	return 0;
}