记录编号	314816	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	1.169 s
提交时间	2016-10-04 08:02:51	内存使用	25.50 MiB

#include "cstdio"
#include "cstring"
#include "iostream"
using namespace std;

const int maxnumber = 300100;
int n, m, maxn;
struct Edge{
	int to, next, w;
	int sum;
}edges[maxnumber*2];
int head[maxnumber], tot;
int value[maxnumber], dis[maxnumber], size[maxnumber], depth[maxnumber], son[maxnumber], fa[maxnumber];
int top[maxnumber], dfn[maxnumber], id[maxnumber], dfsclock;
int cost[maxnumber], begin[maxnumber], end[maxnumber];//cost[i]: 第i个任务的花费
int finite[maxnumber];
// finite[i]:差分数组, 差分每条边被经过的次数	finite/'fainait/

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

void DFS1(const int& a)
{
	size[a] = 1;
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to, w = edges[i].w;
		if(to == fa[a]) continue;
		value[to] = w;
		dis[to] = dis[a] + w;
		fa[to] = a;
		depth[to] = depth[a] + 1;
		DFS1(to);
		size[a] += size[to];
		if(size[to] > size[son[a]]) son[a] = to;
	}
}

void DFS2(const int& a, const int& tp)
{
	top[a] = tp;
	dfn[a] = ++dfsclock;
	id[dfsclock] = a;
	if(son[a]) DFS2(son[a], tp);
	for(int i = head[a]; i; i = edges[i].next){
		int to = edges[i].to;
		if(to == fa[a] || to == son[a]) continue;
		DFS2(to, to);
	}
}

inline int LCA(int s, int t)
{
	int f1 = top[s], f2 = top[t];
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2); swap(s, t);
		}
		s = fa[f1];
		f1 = top[s];
	}
	if(depth[s] < depth[t]) swap(s, t);//lca:t
	return t;
}

inline void Mark(int s, int t)
{
	int f1 = top[s], f2 = top[t];
	while(f1 != f2){
		if(depth[f1] < depth[f2]){
			swap(f1, f2); swap(s, t);
		}
		finite[dfn[f1]]++; finite[dfn[s]+1]--;
		// 差分数组区间加1: 起点值++, (终点+1)值-- 
		s = fa[f1];
		f1 = top[s];
	}
	if(depth[s] < depth[t]) swap(s, t);
	finite[dfn[son[t]]]++; finite[dfn[s]+1]--;
}

inline bool Check(const int& mid)
{
	int cnt = 0, tmp = 0;
	// 记录"超时"的任务总数, 当他们经过同一条边时, 就把这条边改为虫洞 
	memset(finite, 0, sizeof(finite));
	for(int i = 1; i <= m; i++){
		if(cost[i] > mid){
			cnt++; 
			Mark(begin[i], end[i]);
		}
	}
	if(!cnt) return 1;
	else{
		for(int i = 1; i <= n; i++) finite[i] += finite[i-1];
		// 差分数组求前缀和可得到原数组
		for(int i = 1; i <= n; i++)
			if(finite[i] == cnt)
				tmp = max(tmp, value[id[i]]);
		if(maxn - tmp > mid) return 0;
		else return 1;
	}
	return 0;
}

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

	Read(n); Read(m);
	int from, to, w;
	for(int i = 1; i < n; i++){
		Read(from); Read(to); Read(w);
		AddEdge(from, to, w);
		AddEdge(to, from, w);
	}
	
	depth[1] = 1;
	DFS1(1);
	DFS2(1, 1);
	int l = 0, r = 0, mid;
	for(int i = 1; i <= m; i++){
		Read(begin[i]); Read(end[i]);
		cost[i] = dis[begin[i]] + dis[end[i]] - 2 * dis[LCA(begin[i], end[i])];
		r = max(r, cost[i]);
	}
	maxn = r;
	while(l <= r){
		mid = (l + r) >> 1;
		// printf("l:%d r:%d mid:%d\n", l, r, mid);
		if(Check(mid)) r = mid - 1;
		else l = mid + 1;
	}
	if(Check(l)) printf("%d\n", l);
	else printf("%d\n", r);
	
#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
	return 0;
}
/*

	6 3 
	1 2 3 
	1 6 4 
	3 1 7 
	4 3 6 
	3 5 5 
	3 6 
	2 5 
	4 5


	11
*/