记录编号	95637	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.294 s
提交时间	2014-04-08 09:47:43	内存使用	7.18 MiB

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;

#define maxn 100007

struct atype
{
    int x, y;
};

multimap<int,int> tmap;
multimap<int,int>::iterator iter;

int now;
int n, m, e;
int f[maxn];
int g[maxn], h[maxn];
int a[maxn];
int b[maxn], c[maxn];
atype d[maxn];
int nd;

int edge[maxn];
int goal[maxn*2], next[maxn*2], cost[maxn*2];
vector<int> army[maxn];

void contact(int u, int v, int w)
{
	++e; goal[e] = v; cost[e] = w;
	next[e] = edge[u]; edge[u] = e;
	++e; goal[e] = u; cost[e] = w;
	next[e] = edge[v]; edge[v] = e;
}

void dfs(int u, int fa)
{
	int v, j;
	j = edge[u];
	while (j) {
		v = goal[j];
		if (v != fa) {
			f[v] = f[u]+cost[j];
			dfs(v,u);
		}
		j = next[j];
	}
	if (g[u] > 0) {
		for (j = 1; j <= g[u]; ++j)
			army[now].push_back(f[u]);
    }
}
int find(int t)
{
	int l, r, mid;
	l = 2; r = a[0];
	while (l+1 < r) {
		mid = (l+r)/2;
		if (t <= f[a[mid]]) r = mid;
		else l = mid;
	}
	if (t <= f[a[l]]) return l;
	return r;
}
int findnum(int u, int t)
{
	int l, r, mid;
	r = army[u].size();
	if (r == 0) return 0;
	l = 0; --r;
	while (l+1 < r) {
		mid = (l+r)/2;
		if (army[u][mid] <= t) l = mid;
		else r = mid;
	}
	if (army[u][r] <= t) return r+1;
	else if (army[u][l] <= t) return l+1;
	return 0;
}
void dfs2(int u, int fa)
{
	int v,j;
	a[++a[0]] = u;
	if (g[u] > 0) {
		j = find(f[u]-now);
		h[a[j]] += g[u];
	}
	j = edge[u];
	while (j) {
		v = goal[j];
		if (v != fa) {
			dfs2(v,u);
		}
		j = next[j];
	}
	--a[0];
}
bool cmp(int p, int q)
{
	return (p > q);
}
bool cmpd(atype p, atype q)
{
	return (p.y < q.y);
}
bool checkblock(int u, int fa)
{
	int j, v;
	bool ok;
	ok = false;
	j = edge[u];
	while (j) 
	{
		v = goal[j];
		if (v != fa) 
		{
			ok = true;
			if (h[v] == 0 && !checkblock(v,u))
				return false;
		}
		j = next[j];
	}
	return ok;
}
bool check(int time)
{
	int i, j, k, u, v, t;
	bool ok;
	bool tok;
	
	memset(h,0,sizeof(h));
	a[0] = 0; 
	now = time;
	dfs2(1,0);

	b[0] = 0; c[0] = 0; nd = 0;
	u = 1; j = edge[u];    
	while (j) 
	{
		v = goal[j];
		ok = checkblock(v,1);
		tok = false;
		if (!ok && h[v] == 0)
			c[++c[0]] = cost[j];
		else {
			k = findnum(v,time-cost[j]);
			if (h[v] == k && !ok) 
			{
				--k;
				tok = true;
			}
			t = 0;
			while (k > 0) 
			{
				--k;
				b[++b[0]] = army[v][t++]-time+cost[j];
			}
			if (tok) 
			{
				++nd;
				d[nd].x = cost[j];
				d[nd].y = army[v][t]-time+cost[j];
				++t;
			}
		}
		j = next[j];
	}
    
	tmap.clear();
	for (i = 1; i <= b[0]; ++i)
		tmap.insert(multimap<int,int>::value_type(-b[i],0));
	for (i = 1; i <= nd; ++i) 
	{
		iter = tmap.lower_bound(d[i].x);
		if (iter == tmap.end()) continue;
		if (d[i].y < -iter->first) 
		{
			tmap.erase(iter);
			tmap.insert(multimap<int,int>::value_type(-d[i].y,0));
		}
	}
    
	iter = tmap.begin();
	for (i = 1; i <= b[0]; ++i)
	{
		b[i] = -iter->first;
		iter++;
	}
    
	sort(b+1,b+b[0]+1);
	sort(c+1,c+c[0]+1,cmp);
	if (b[0] < c[0]) return false;
	for (i = 1; i <= c[0]; ++i)
		if (c[i]+b[i] > 0)
			return false;
	return true;
}
int main()
{
	freopen("blockade.in","r",stdin);
	freopen("blockade.out","w",stdout);
	
	int i, j;
	int u,v,w;
	int l,r,mid;
	
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	e = 1;
	memset(edge,0,sizeof(edge));
	
	scanf("%d",&n);
	l = 0; r = 0;
	for (i = 1; i < n; ++i) {
		scanf("%d%d%d",&u,&v,&w);
		contact(u,v,w);
		if (w > r) r = w;
	}
	scanf("%d",&m);
	for (i = 1; i <= m; ++i) {
		scanf("%d",&u);
		++g[u];
	}

	j = edge[1];
	while (j) {
		v = goal[j];
		now = v;
		army[now].clear();
		dfs(v,1);
		sort(army[now].begin(),army[now].end());
		w = army[now].size();
		if (w > 0 && army[now][w-1] > r) {
			r = army[now][w-1];
		}
		j = next[j];
	}
	r += r+r;
	
	while (l+1 < r) {
		mid = (l+r)/2;
		if (check(mid)) r = mid;
		else l = mid;
	}
	if (!check(l))
		if (!check(r)) printf("%d\n",-1);
		else printf("%d\n",r);
	else
		printf("%d\n",l);
	return 0;
}