记录编号	130597	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.154 s
提交时间	2014-10-22 19:44:05	内存使用	2.22 MiB

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <set>
using namespace std;

#if defined DEBUG
FILE *in = fopen("test", "r");
#define out stdout
#else
FILE *in = fopen("blockade.in","r");
FILE *out = fopen("blockade.out","w");
#endif
/*==============================================*/
#define maxn ((int)5e4 + 5)
#define pb push_back
#define iter vector<edge>::iterator

struct edge{
	int to, w;
	edge(int T,int W):to(T),w(W){}
};

struct army{
	int restT, newT, loc;
}temp[maxn];
int tempcnt;

void getint(int &k){
	char c;
	while(!isdigit(c))c = fgetc(in);
	k = c - '0';
	while(isdigit(c = fgetc(in)))k = k * 10 + c - '0';
}

int n, m, L = 0, R = 0;
int dis[maxn]={0}, root[maxn], pre[maxn], armyloc[maxn];
vector<edge> adj[maxn];

void DFS(int k){//预处理dis,root和pre
	iter it;
	for(it = adj[k].begin();it < adj[k].end();++it){
		if(it->to == pre[k])continue;
		dis[it->to] = dis[k] + it->w;
		root[it->to] = root[k];
		pre[it->to] = k;
		DFS(it->to);
	}
}

bool operator <(const edge&a,const edge&b){
	return dis[a.to] < dis[b.to];
}

bool init(){//0: no answer
	int i,u,v,w;
	getint(n);
	for(i = 1;i < n;++i){
		getint(u),getint(v),getint(w);
		adj[u].pb(edge(v,w));
		adj[v].pb(edge(u,w));
	}
	getint(m);
	if(m < (int)adj[1].size())return 0;
	iter it = adj[1].begin();
	for(;it < adj[1].end();++it){
		root[it->to] = it->to;
		pre[it->to] = 1;
		dis[it->to] = it->w;
		DFS(it->to);
	}
	for(i = 0;i < m;++i){getint(armyloc[i]);R = max(R, dis[armyloc[i]]);}
	sort(adj[1].begin(), adj[1].end());
	R += dis[(adj[1].end()-1)->to];
	return 1;
}

bool Acmp(const army&a, const army&b){//按到达首都后的剩余时间排序
	return a.newT < b.newT;
}

bool check(int k){
	int i,j;
	iter it;
	tempcnt = 0;
	bool ctrled[maxn] = {0};
	for(i = 0;i < m;++i){//贪心上行
		j = armyloc[i];
		while(pre[j] != 1 && dis[armyloc[i]] - dis[pre[j]] <= k)
			j = pre[j];
		if(pre[j] != 1){
			while(pre[j] != 1){//j到root[j]是否是一条链,如果是则直接设置ctrled
				if((int)adj[pre[j]].size() > 2)break;
				j = pre[j];
			}
			if(pre[j] == 1)ctrled[j] = 1;
		}
		else{
			temp[tempcnt].newT = k - dis[armyloc[i]];
			temp[tempcnt].loc = j;
			temp[tempcnt++].restT = k - dis[armyloc[i]] + dis[j];
		}
	}
	multiset<int> Free;
	multiset<int>::iterator it_S;
	sort(temp, temp + tempcnt, Acmp);
	for(i = 0;i < tempcnt;++i){//是否要暂时到首都部署(Free维护要到首都的军队的剩余时间)
		int newT = temp[i].restT - dis[temp[i].loc];
		if(!ctrled[temp[i].loc]){
			if(!Free.empty()){//用temp[i]替换在首都的更无用的军队
				it_S = Free.lower_bound(dis[temp[i].loc]);
				if(it_S != Free.end() && *it_S < temp[i].newT){
					Free.erase(it_S);
					Free.insert(temp[i].newT);
				}
			}
			ctrled[temp[i].loc] = 1;
		}
		else if(newT >= 0)//已被更无用的军队控制,果断来到首都部署
			Free.insert(temp[i].newT), temp[i].restT = newT;
	}
	for(it_S = Free.begin(),it = adj[1].begin();it < adj[1].end();++it){
		if(ctrled[it->to])continue;
		while(it_S != Free.end() && *it_S < it->w)++it_S;
		if(it_S == Free.end())return 0;
		++it_S;
	}
	return 1;
}

int main(){
	int k;
	if(!init()){fprintf(out,"-1\n");return 0;}
	while(L <= R){//二分查找
		k = (L >> 1) + (R >> 1) + (L & R & 1);
		if(check(k))R = k - 1;
		else L = k + 1;
	}
	fprintf(out,"%d\n",L);
	return 0;
}