记录编号	442763	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2015]运输计划	最终得分	100
用户昵称	Imone NOI2018Au	是否通过	通过
代码语言	C++	运行时间	1.667 s
提交时间	2017-08-28 15:35:00	内存使用	24.61 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 300010;

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

int N, M;
struct path {
	int u, v, lca, d;
	inline bool operator<(path rhs) const {
		return d > rhs.d;
	}
} P[MAXN];

int head[MAXN], next[2*MAXN], tail[2*MAXN], len[2*MAXN], id = 1;
int Lh[MAXN], Ln[2*MAXN], Lt[2*MAXN], Lid = 1;
inline void link(int u, int v, int d) {
	next[id] = head[u]; tail[id] = v; len[id] = d; head[u] = id++;
}
inline void Llink(int u, int v) {
	Ln[Lid] = Lh[u]; Lt[Lid] = v; Lh[u] = Lid++;
}

int dist[MAXN], fa[MAXN], falen[MAXN];
void dfs(int u, int f, int d) {
	int i, v;
	fa[u] = f; dist[u] = d;
	for(i=head[u];i;i=next[i]) {
		v = tail[i];
		if(v != f) falen[v] = len[i], dfs(v, u, d + len[i]);
	}
}
int set[MAXN];
inline int find(int x) {
	return (x == set[x]) ? x : (set[x] = find(set[x]));
}
bool vis[MAXN];
void tarjan(int u) {
	int i, v, id;
	vis[u] = 1;
	for(i=Lh[u];i;i=Ln[i]) if(vis[Lt[i]]) {
		id = (i + 1) >> 1;
		P[id].lca = find(Lt[i]);
		P[id].d = dist[P[id].u] + dist[P[id].v] - 2 * dist[P[id].lca];
	}
	for(i=head[u];i;i=next[i]) if(!vis[v = tail[i]]) tarjan(v), set[v] = u;
}
int tag[MAXN];
void getmark(int u) {
	int i, v;
	for(i=head[u];i;i=next[i]) {
		v = tail[i];
		if(v != fa[u]) getmark(v), tag[u] += tag[v];
	}
}

bool ok(int d) {
	if(d >= P[1].d) return 1;

	int i, ctr = 0;
	memset(tag, 0, sizeof(tag));
	for(i=1;i<=M;i++) {
		if(d >= P[i].d) break;
		tag[P[i].u]++; tag[P[i].v]++;
		tag[P[i].lca] -= 2;

		ctr++;
	}
	getmark(1);

	for(i=1;i<=N;i++) if(tag[i] == ctr && P[1].d - falen[i] <= d) return 1;
	return 0;
}

int main() {
    int size = 128 << 20;
    char *p = (char*)malloc(size) + size;  
    __asm__("movl %0, %%esp\n" :: "r"(p));

	freopen("transport.in", "rt", stdin);
	freopen("transport.out", "wt", stdout);
	
	int i, u, v, d;
	read(N); read(M);
	for(i=1;i<N;i++) {
		read(u); read(v); read(d);
		link(u, v, d); link(v, u, d);
	}
	for(i=1;i<=M;i++) {
		read(u); read(v); P[i] = {u, v};
		Llink(u, v); Llink(v, u);
	}
	//initialize set
	for(i=1;i<=N;i++) set[i] = i;
	dfs(1, 0, 0); tarjan(1);
	//sort path
	sort(P+1, P+M+1);
	//bin search
	int L = 1, R = P[1].d; //(L, R]
	while(R - L > 1) {
		int mid = (L + R) >> 1;
		if(ok(mid)) R = mid; else L = mid;
	}
	printf("%d", R);
}