记录编号	328797	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Tiny	是否通过	通过
代码语言	C++	运行时间	0.942 s
提交时间	2016-10-24 16:48:22	内存使用	22.03 MiB

#include "stdio.h"
#include "string.h"

template <typename T> inline void Read(T &num) {
	num = 0; char ch; bool minus = false;
	while (ch = getchar(), ch < '-' || ch > '9');
	if (ch == '-') { minus = true; ch = getchar(); }
	while (num = num * 10 + ch - '0', ch = getchar(), ch >= '0' && ch <= '9');
	if (minus) num = -num;
}

const size_t MAXN = 300000 + 10;

int n, m, maxc;
struct Edge { int v, w, ne; } E[MAXN << 1];
int head[MAXN], tot_e = 0;
struct Node { int ch, fa, sz, w, dep, dfn, dis, top; } N[MAXN];
int p[MAXN][2], c[MAXN];
int s[MAXN];

inline void Insert(const int &u, const int &v, const int &w) {
	E[++tot_e] = (Edge){v, w, head[u]}; head[u] = tot_e;
}

inline void DFS(const int &rt) {
	N[rt].sz = 1; N[rt].ch = 0;
	for (int i = head[rt], v; i; i = E[i].ne) {
		v = E[i].v;
		if (N[v].sz) continue;
		N[v].fa = rt;
		N[v].dep = N[rt].dep + 1;
		N[v].w = E[i].w;
		N[v].dis = N[rt].dis + E[i].w;
		DFS(v);
		N[rt].sz += N[v].sz;
		if (N[v].sz > N[N[rt].ch].sz) N[rt].ch = v;
	}
}

inline void DFS(const int &rt, const int &t) {
	static int dfs_time;
	N[rt].top = t; N[rt].dfn = ++dfs_time;
	if (N[rt].ch) DFS(N[rt].ch, t);
	for (int i = head[rt], v; i; i = E[i].ne) {
		v = E[i].v;
		if (v != N[rt].fa && v != N[rt].ch) DFS(v, v);
	}
}

inline int Dis(int a, int b) {
	int a0 = a, b0 = b;
	while (N[a].top != N[b].top) {
		if (N[N[a].top].dep < N[N[b].top].dep)
			a ^= b ^= a ^= b;
		a = N[N[a].top].fa;
	}
	int lca = (N[a].dep < N[b].dep ? a : b);
	return (N[a0].dis + N[b0].dis - (N[lca].dis << 1));
}

inline void Set_Mark(int a, int b) {
	while (N[a].top != N[b].top) {
		if (N[N[a].top].dep < N[N[b].top].dep)
			a ^= b ^= a ^= b;
		++s[N[N[a].top].dfn]; --s[N[a].dfn + 1];
		a = N[N[a].top].fa;
	}
	if (N[a].dep > N[b].dep) a ^= b ^= a ^= b;
	++s[N[N[a].ch].dfn]; --s[N[b].dfn + 1];
}

inline bool Judge(const int &t) {
	memset(s, 0, sizeof(s));
	int cnt = 0;
	for (int i = 1; i <= m; ++i) if (c[i] > t)
		{ ++cnt; Set_Mark(p[i][0], p[i][1]); }
	if (cnt == 0) return true;
	for (int i = 2; i <= n; ++i) s[i] += s[i - 1];
	for (int i = 2; i <= n; ++i)
		if (s[N[i].dfn] == cnt && maxc - N[i].w <= t)
			return true;
	return false;
}

int main() {
 #define SUBMIT
 #ifdef SUBMIT
	freopen("transport.in", "r", stdin);
	freopen("transport.out", "w", stdout);
 #endif

	Read(n); Read(m);
	for (int i = 1, u, v, w; i < n; ++i) {
		Read(u); Read(v); Read(w);
		Insert(u, v, w); Insert(v, u, w);
	}
	memset(N, 0, sizeof(N));
	N[1].dep = 1; DFS(1); DFS(1, 1);
	for (int i = 1; i <= m; ++i) {
		Read(p[i][0]); Read(p[i][1]);
		c[i] = Dis(p[i][0], p[i][1]);
		if (c[i] > maxc) maxc = c[i];
	}
	int l = 0, r = maxc, mid;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (Judge(mid)) r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", l);

 #ifndef SUBMIT
	puts("\n--------------------");
	getchar(); getchar();
 #else
	fclose(stdin); fclose(stdout);
 #endif
	return 0;
}