记录编号	345322	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	2.192 s
提交时间	2016-11-10 22:31:37	内存使用	17.85 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
//#define DBG
#ifdef DBG
#include <iostream>
#endif
#define dbg(x) std::cout << #x << " : " << x << "\n"
#define file(x) "transport." #x
using std::max;
using std::swap;
namespace I{
	const int L = 1 << 15;
	char buf[L], *s, *t;
	inline char gc() {
		if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
		if (s == t) return EOF;
		else return *s++;
	}
	inline int gi() {
		int s = 0, ch = gc();
		while (!(ch <= '9' && ch >= '0')) ch = gc();
		while (ch <= '9' && ch >= '0') s = s*10 + ch - '0', ch = gc();
		return s;
	}
}using I::gi;
const int V = 3e5 + 10, E = V << 1;
struct EDGE{int u, v, w;}st[E];
int hed[V], nxt[E], n, m;
struct PL {
	int u, v;
}pl[V];
inline void _add(int u, int v, int w) {
	static int sz = 0;
	st[++sz].u = u, st[sz].v = v, st[sz].w = w;
	nxt[sz] = hed[u], hed[u] = sz;
}
void add(int u, int v, int w) {
	_add(u, v, w), _add(v, u, w);
}
int fa[V], son[V], sz[V], top[V], fae[V], da[V], dep[V], nd[V], wsum[V], dfn[V], dfsclk;
int dfs1(int u) {
	int v;
	sz[u] = 1;
	for (int e = hed[u]; e; e = nxt[e]) if((v = st[e].v) != fa[u]) {
		fa[v] = u;
		fae[v] = e ;
		dep[v] = dep[u] + 1;
		wsum[v] = wsum[u] + st[e].w;
		sz[u] += dfs1(v);
		if (sz[v] > sz[son[u]]) son[u] = v;
	}
	return sz[u];
}
void dfs2(int u,int nt) {
	dfn[u] = ++dfsclk;
	top[u] = nt;
	int v;
	if (son[u]) dfs2(son[u], nt);
	for (int e = hed[u]; e; e = nxt[e]) if((v = st[e].v) != fa[u] && v != son[u]) {
		dfs2(v, v);
	}
}
int maxw, pcnt, maxnd, val[V];
bool check(int now) {
	memset(da, 0, sizeof(da));
	maxw = pcnt = 0;
	for (int i = 1; i <= m; i++) if(nd[i] > now) {
		++pcnt;
		int u = pl[i].u, v = pl[i].v;
		while (top[u] != top[v]) {
			if (dep[top[u]] < dep[top[v]]) swap(u, v);
			--da[dfn[u] + 1], ++da[dfn[top[u]]];
			u = fa[top[u]];
		}
		if (dep[u] < dep[v]) swap(u, v);
		++da[dfn[son[v]]], --da[dfn[u] + 1];
	}
	if (!pcnt) return true;
	for (int i = 1; i <= n; i++) if ((da[i] += da[i - 1]) == pcnt && maxnd - val[i] <= now) return true;
	return false;
}
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	n = gi(), m = gi();
	int l = 0, r = 0, mid;
	for (int i = 1; i < n; i++) {
		int u = gi(), v = gi(), w = gi();
		add(u, v, w);
	}
	dfs1(1), dfs2(1, 1);
	for (int i = 1; i <= m; i++) {
		int u = pl[i].u = gi(), v = pl[i].v = gi();
		while (top[u] != top[v]) {
			if (dep[top[u]] < dep[top[v]]) swap(u, v);
			u = fa[top[u]];
		}
		if (dep[u] < dep[v]) swap(u, v);
		nd[i] += wsum[pl[i].u] + wsum[pl[i].v] - 2*wsum[v];
		r = max(r, nd[i]);
#ifdef DBG
		dbg(i);
		dbg(nd[i]);
#endif
	}
	maxnd = r;
	for (int i = 2; i <= n; i++) val[dfn[i]] = st[fae[i]].w;
	while (l < r) {
		mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
}