记录编号	211191	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	zhengtn03	是否通过	通过
代码语言	C++	运行时间	1.368 s
提交时间	2015-11-30 17:53:38	内存使用	37.63 MiB

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<sstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;

#define maxn 300010
char *in = (char*)malloc(10000000);
inline int scan()
{
	int x;
	char c = *(in++);
	bool minus = 0;
	while (!isdigit(c) && c != '-')c = *(in++);
	if (c == '-')minus = 1, c = *(in++);
	x = c - '0';
	while (isdigit(c = *(in++)))x = x * 10 + c - '0';
	if (minus)x = -x;
	return x;
}

int head[maxn];
int p[maxn << 1];
int next1[maxn << 1];
int t[maxn << 1];
int edgecnt;

int u1[maxn];
int v1[maxn];

int father[maxn];

int DfsOrder[maxn];
int DfsOrderNumber;
int FirstDfsOrder[maxn];
int FirstDfsOrderNumber;
int fatherEdge[maxn];

int childSizeMax[maxn];
int maxChildEdge[maxn];
int heavyEdge[maxn << 1];
int size1[maxn];

int topChainPoint[maxn];
int pointDeep[maxn];
int dep[maxn];
int lcaUV[maxn];

int w[maxn];
int cnt[maxn << 1];
int pointCnt[maxn];

void addedge(int u, int v, int w)// 添加边(u,v)
{
	edgecnt++;
	p[edgecnt] = v;
	next1[edgecnt] = head[u];
	t[edgecnt] = w;
	head[u] = edgecnt;
}

void DFS0(int point)
{
	FirstDfsOrder[FirstDfsOrderNumber] = point;
	FirstDfsOrderNumber++;
	int nextEdge = head[point];
	while (nextEdge != 0)
	{
		int nextPoint = p[nextEdge];
		if (father[nextPoint] == 0)
		{
			fatherEdge[nextPoint] = nextEdge;
			father[nextPoint] = point;
			DFS0(nextPoint);
		}
		nextEdge = next1[nextEdge];
	}
	DfsOrder[DfsOrderNumber] = point;
	DfsOrderNumber++;
}

void NotDfs(int n)
{
	for (int i = 0; i < DfsOrderNumber; i++)
	{
		int point = DfsOrder[i];
		if (maxChildEdge[point] != 0)
		{
			heavyEdge[maxChildEdge[point]] = 1;
		}
		size1[point]++;
		int fatherPoint = father[point];
		if (fatherPoint != -1)
		{
			size1[fatherPoint] += size1[point];
			if (size1[point] > childSizeMax[fatherPoint])
			{
				childSizeMax[fatherPoint] = size1[point];
				maxChildEdge[fatherPoint] = fatherEdge[point];
			}
		}
	}
}

void NotDfs1()
{
	for (int i = 0; i < FirstDfsOrderNumber; i++)
	{
		int point = FirstDfsOrder[i];
		int fatherPoint = father[point];
		if (fatherPoint != -1)
		{
			pointDeep[point] = pointDeep[fatherPoint] + 1;
			dep[point] = dep[fatherPoint] + t[fatherEdge[point]];
			if (heavyEdge[fatherEdge[point]] == 1)
			{
				topChainPoint[point] = topChainPoint[fatherPoint];
			}
			else
			{
				topChainPoint[point] = point;
			}
		}
	}
}

inline int LCA(int point1, int point2)
{
	int ans = 0;
	int f1 = topChainPoint[point1];
	int f2 = topChainPoint[point2];
	while (f1 != f2)
	{
		if (pointDeep[f1] < pointDeep[f2])
		{
			swap(point1, point2);
			swap(f1, f2);
		}
		if (f1 != point1) point1 = f1;
		else point1 = father[point1];
		f1 = topChainPoint[point1];
		f2 = topChainPoint[point2];
	}
	ans = point1;
	if (pointDeep[point1] > pointDeep[point2])
	{
		ans = point2;
	}
	return ans;
}

void NotDFS4()
{
	for (int i = 0; i < DfsOrderNumber; i++)
	{
		int point = DfsOrder[i];
		int fatherPoint = father[point];
		if (fatherPoint != -1)
		{
			pointCnt[fatherPoint] += pointCnt[point];
			cnt[fatherEdge[point]] = pointCnt[point];
		}
	}
}

int Test1(int ans, int m, int n, int maxW)
{
	for (int i = 0; i <= n; i++)
	{
		pointCnt[i] = 0;
	}
	for (int i = 0; i <= 2 * n; i++)
	{
		cnt[i] = 0;
	}
	int tempSize = 0;
	for (int i = 0; i < m; i++)
	{
		if (w[i]>ans)
		{
			tempSize++;
			pointCnt[u1[i]]++;
			pointCnt[v1[i]]++;
			pointCnt[lcaUV[i]] -= 2;
		}
	}
	if (tempSize == 0) return 1;
	NotDFS4();
	for (int i = 0; i <= 2 * n; i++)
	{
		if (cnt[i] == tempSize && maxW - t[i] <= ans)
		{
			return 1;
		}
	}
	return 0;
}

int main()
{
	freopen("transport.in", "r", stdin);
	freopen("transport.out", "w", stdout);
	fread(in, 1, 10000000, stdin);
	int n, m;
	n = scan();
	m = scan();
	int maxEdgeLength = 0;
	for (int i = 1; i < n; i++)
	{
		int u = scan();
		int v = scan();
		int w = scan();
		maxEdgeLength = max(maxEdgeLength, w);
		addedge(u, v, w);
		addedge(v, u, w);
	}
	for (int i = 0; i < m; i++)
	{
		u1[i] = scan();
		v1[i] = scan();
		if (u1[i]>v1[i]) swap(u1[i], v1[i]);
	}
	father[1] = -1;
	DFS0(1);
	NotDfs(n);
	NotDfs1();
	int maxW = 0;
	for (int i = 0; i < m; i++)
	{
		lcaUV[i] = LCA(u1[i], v1[i]);
		w[i] = dep[u1[i]] + dep[v1[i]] - 2 * dep[lcaUV[i]];
		maxW = max(maxW, w[i]);
	}
	int left1 = maxW - maxEdgeLength - 1;
	int right1 = maxW;
	while (right1 - left1 > 1)
	{
		int mid = (right1 + left1) >> 1;
		if (Test1(mid, m, n, maxW)) right1 = mid;
		else left1 = mid;
	}
	printf("%d\n", right1);
	return 0;
}