记录编号	304162	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.920 s
提交时间	2016-09-07 18:00:26	内存使用	13.52 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 2e9;
const int maxn = 5e4 + 10;
const int root = 1;


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


struct Edge {
	int to, ne, v;
	Edge() {}
	Edge(int to_, int ne_, int v_) { to = to_, ne = ne_, v = v_; }
}e[maxn << 1];
int head[maxn], ecnt;
inline void add_edge(int fr, int to, int v) {
	e[++ecnt] = Edge(to, head[fr], v), head[fr] = ecnt;
	e[++ecnt] = Edge(fr, head[to], v), head[to] = ecnt;
}


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


struct Army {
	int pos, dis;
	bool use;
	Army() {}
	Army(int pos_, int dis_) { pos = pos_, dis = dis_, use = false; }
	
	bool operator < (const Army &b) const { return dis < b.dis; }
}as[maxn];


int mul_fa[maxn][17];
LL mul_dis[maxn][17];
int deep[maxn];
LL max_dis;
int n, m;


void get_mul(int now) {
	ns[now] = Node(deep[now], now);
	for(int i = 1; i <= 16; i++) {
		if(deep[now] < 1 << i) {
			mul_dis[now][i] = inf;
			continue;
		}
		
		int now_fa = mul_fa[now][i - 1];
		mul_fa[now][i] = mul_fa[now_fa][i - 1];
		mul_dis[now][i] = mul_dis[now_fa][i - 1] + mul_dis[now][i - 1];
		max_dis = max(max_dis, mul_dis[now][i]); 
	}
	
	for(int i = head[now]; i; i = e[i].ne) {
		int to = e[i].to;
		if(deep[to] or to == root) continue;
		
		deep[to] = deep[now] + 1;
		mul_fa[to][0] = now;
		mul_dis[to][0] = e[i].v;
		
		get_mul(to);
	}
}


Node un_c[maxn]; // uncontroled dis
int uc_top;
Army re_a[maxn]; // army left dis
int ra_top;
bool is_c[maxn]; // is controled 


inline LL query_dis(int now, int delta) { // 到往上delta层的父节点的距离 
	LL dis = 0;
	for(int i = 0; i <= 16; i++) {
		if(delta & (1 << i))
			dis += mul_dis[now][i], now = mul_fa[now][i];
	}
	return dis;
}


inline int query_fa(int now, int delta) { // 向上delta层 
	for(int i = 0; i <= 16; i++) if(delta & (1 << i)) now = mul_fa[now][i];
	return now;
}


inline bool check(int lim) {
	memset(is_c, 0, sizeof(is_c));

	uc_top = ra_top = 0;
	
	for(int i = 1; i <= m; i++) {
		int now = as[i].pos; // 军队开始位置 
		
		int l = 0, r = deep[now], mid, ans;
		LL dis;
		while(l + 1 < r) {
			mid = (l + r) >> 1;
			
			dis = query_dis(now, mid); 
			
			if(dis <= lim) l = mid; //找到小于限制的最大距离 
			else r = mid - 1;
		}
		
		if((dis = query_dis(now, r)) <= lim) ans = r;
		else if((dis = query_dis(now, r - 1)) <= lim) ans = r - 1;
		else dis = query_dis(now, l), ans = l;
		
		if(ans == deep[now]) { // 如果能到达根节点 
			int re_top = query_fa(now, deep[now] - 1); // 最浅的第二层节点 
			re_a[++ra_top] = Army(re_top, lim - dis);
		} else { // 在之前某一节点停止 
			int tar = query_fa(now, ans);
			is_c[tar] = true;
		}
	}
	
	for(int i = n; i >= 1; i--) {
		int now = ns[i].pos, fa;
		if(now == root) continue;
		
		bool son_st = false;
		if(not is_c[now]) {
			is_c[now] = true;
			
			for(int j = head[now]; j; j = e[j].ne) {
				if(e[j].to != mul_fa[now][0]) {
					son_st = true;
					if(not is_c[e[j].to]) is_c[now] = false;
				}
			}
			
			if(not son_st) is_c[now] = false;
		}
		
		if(deep[now] == 1 and not is_c[now]) {
			fa = query_fa(now, deep[now] - 1);
			un_c[++uc_top] = Node(mul_dis[now][0], fa);
		}
	}
	
	if(uc_top > ra_top) return false;
	else {
		sort(un_c + 1, un_c + uc_top + 1);
		sort(re_a + 1, re_a + ra_top + 1);
		
		int j = 1;
		for(int i = 1; i <= ra_top; i++) {
			while(is_c[un_c[j].pos]) j++;
			if(not is_c[re_a[i].pos]) is_c[re_a[i].pos] = true;
			else if(un_c[j].de <= re_a[i].dis and not is_c[un_c[j].pos]) {
				is_c[un_c[j].pos] = true;
				j++;
			}
		}
		
		for(int i = 1; i <= uc_top; i++) {
			if(is_c[un_c[i].pos]) continue;
			return false;
		}
		return true;
	}
}


inline void read() {
	n = get_num();
	int fr, to, v;
	for(int i = 1; i <= n - 1; i++) {
		fr = get_num();
		to = get_num();
		v = get_num();
		
		add_edge(fr, to, v);
	}
	
	m = get_num();
	for(int i = 1; i <= m; i++) {
		int pos = get_num();
		as[i].pos = pos;
	}
}


inline void solve() {
	get_mul(root);
	sort(ns + 1, ns + n + 1);
	LL l = 0, r = inf, mid, ans;
	
	check(10);
	
	while(l + 1 < r) {
		mid = (l + r) >> 1;
		
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	
//	printf("l = %lld r = %lld\n", l, r);
	if(check(l)) ans = l;
	else if(check(l + 1)) ans = l + 1;
	else ans = r;
	
	printf("%lld\n", ans == inf ? -1 : ans);
}


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