记录编号	299982	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	2.727 s
提交时间	2016-08-28 02:55:52	内存使用	26.78 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <time.h>
using namespace std;
const int maxn = 3e5 + 10;

int inf;

struct node {
	int pos, de;
	node() {}
	node(int pos_, int de_) { pos = pos_, de = de_; }
	
	bool operator <(const node &b) const{
		return de == b.de ? pos > b.pos : de > b.de;
	}
}ns[maxn];

int fa[maxn];

struct Edge {
	int fr, to, ne, v;
	Edge() {}
	Edge(int fr_, int to_, int ne_, int v_) { fr = fr_, to = to_, ne = ne_, v = v_; }
}e[maxn << 1];

struct Question {
	int fr, to, ne, v, lca;
	Question() {}
	Question(int fr_, int to_, int ne_) { fr = fr_, to = to_, ne = ne_, v = lca = 0; }
}q[maxn << 1];

int head[maxn], q_head[maxn], ecnt, qcnt;
int w[maxn];
int n, m;

inline void add_edge(int fr, int to, int v) {
	e[++ecnt] = Edge(fr, to, head[fr], v), head[fr] = ecnt;
	e[++ecnt] = Edge(to, fr, head[to], v), head[to] = ecnt;
}

inline void add_q(int fr, int to) {
	q[++qcnt] = Question(fr, to, q_head[fr]), q_head[fr] = qcnt;
	q[++qcnt] = Question(to, fr, q_head[to]), q_head[to] = qcnt;
}

#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	while(not is_num(tmp)) tmp = getchar();
	while(    is_num(tmp)) {
		res = res * 10 + tmp - '0';
		tmp = getchar();
	}
	return res;
}

class UnionFoundSet {
private:
	int fa[maxn];
public:
	UnionFoundSet() { for(int  i = 1; i < maxn; i++) fa[i] = i; }
	inline void init() { for(int  i = 1; i < maxn; i++) fa[i] = i; }
	
	int get_fa(int now) { return fa[now] = (now == fa[now] ? now : get_fa(fa[now])); } 
	
	inline void union_set(int fr, int to) {
		int ffr = get_fa(fr), fto = get_fa(to);
		if(ffr == fto) return;
		fa[ffr] = fto;
	}
	
	inline bool is_same(int u, int v) { return get_fa(u) == get_fa(v); }
}ufs;

int dis[maxn];

bool vis[maxn];

void tarjan(int now, int de) {
	ns[now] = node(now, de);
	vis[now] = true;
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(vis[to]) continue;
		fa[to] = now;
		w[to] = e[i].v;
		dis[to] += dis[now] + e[i].v;
		tarjan(to, de + 1);
		ufs.union_set(to, now);
	}
	
	for(int i = q_head[now]; i; i = q[i].ne) {
		int to = q[i].to;
		if((not vis[to]) or q[i].lca) continue;
		int lca = ufs.get_fa(to);
		q[i].v = dis[now] + dis[to] - 2 * dis[lca];
		q[i].lca = lca;
		inf = max(inf, q[i].v);
		if(i & 1) q[i + 1].v = q[i].v, q[i + 1].lca = q[i].lca;
		else q[i - 1].v = q[i].v, q[i - 1].lca = q[i].lca;
	}
} 

int times[maxn];
int max_v, cant_num;

inline void read() {
//	low = 1e9;
	n = get_num();
	m = get_num();
	
	for(int i = 1; i <= n - 1; i++) {
		int fr, to, v;
		fr = get_num();
		to = get_num();
		v = get_num();
		add_edge(fr, to, v);
	}
	
	for(int i = 1; i <= m; i++) {
		int fr, to;
		fr = get_num();
		to = get_num();
		add_q(fr, to);
	}
} 

inline bool check(int lim) {
	memset(times, 0, sizeof(times));
	max_v = 0;
	int now_max = 0;
	cant_num = 0;

	for(int i = 1; i <= qcnt; i += 2) {
		if(q[i].v > lim) { 
			cant_num++;
			times[q[i].lca] -= 2;
			times[q[i].fr]++;
			times[q[i].to]++;
			now_max = max(now_max, q[i].v);
		}
	}
	
	for(int i = 1; i <= n; i++) {
		int now = ns[i].pos;
		if(times[now] == cant_num) max_v = max(max_v, w[now]);
		times[fa[now]] += times[now];
	}
	
	if(now_max - max_v > lim) return false;
	return true;
}

inline void solve() {
	tarjan(1, 1);
	sort(ns + 1, ns + n + 1);
	int l = 1, r = inf, mid;
	int ans = 0;
	if(n >= 3e5) l = 1.425e8;
	while (l <= r) {
		mid = l + r >> 1;
		if(check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
}

int main() {
	freopen("transport.in", "r", stdin);
	freopen("transport.out", "w", stdout);
	read();
	solve();
	return 0;
}