记录编号	73214	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.646 s
提交时间	2013-10-20 18:20:14	内存使用	4.32 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
#define ROOT 1
typedef long long ll;
const ll SIZEN=50010;
const ll INF=5e7;
ll n,m;
vector<pair<ll,ll> > c[SIZEN];
ll root_son[SIZEN]={0};
ll father[SIZEN]={0};
ll fatherlen[SIZEN]={0};
ll army_station[SIZEN]={0};
ll ori_stationed[SIZEN]={0};//某个节点最初驻军数
ll now_stationed[SIZEN]={0};//某个节点当前驻军数
class MB_ARMY{
public:
	ll ic;//从哪个子节点前来
	ll lt;//剩余时间
};
bool operator < (MB_ARMY a,MB_ARMY b){
	return a.lt<b.lt;
}
multiset<MB_ARMY> nation_mobile_army;//到达首都的军队之集
multiset<ll> local_mobile_army[SIZEN];//到达首都某子节点的军队之集,键值是剩余时间
bool check_control(ll x){//检测x之子树是否被控制
	if(now_stationed[x]>0) return true;//有驻军
	if(c[x].size()==1) return false;
	ll i;
	#define now c[x][i]
	for(i=0;i<c[x].size();i++){
		if(now.first==father[x]) continue;
		if(!check_control(now.first)) return false;
	}
	return true;
}
void single_climb(ll x,ll lefttime){//驻扎在x的军队在lefttime时间内向首都尽量移动
	if(fatherlen[x]>lefttime){
		return;//无法继续向首都移动
	}
	if(x==ROOT){
		nation_mobile_army.insert((MB_ARMY){0,lefttime});
		return;
	}
	if(father[x]==ROOT){//可以走到首都
		nation_mobile_army.insert((MB_ARMY){x,lefttime-fatherlen[x]});
		local_mobile_army[x].insert(lefttime-fatherlen[x]);
	}
	else{//走向一个普通节点
		now_stationed[x]--;
		now_stationed[father[x]]++;
		single_climb(father[x],lefttime-fatherlen[x]);
	}
}
void all_climb(ll lefttime){//所有军队均在lefttime时间内尽量向首都移动
	ll i;
	for(i=1;i<=m;i++){
		single_climb(army_station[i],lefttime);
	}
}
bool check_feas(ll lefttime){//检查是否能lefttime时间内控制疫情
	ll i;
	nation_mobile_army.clear();
	for(i=1;i<=n;i++) local_mobile_army[i].clear();
	for(i=1;i<=n;i++) now_stationed[i]=ori_stationed[i];
	all_climb(lefttime);
	ll u;
	multiset<MB_ARMY>::iterator nkey;
	multiset<ll>::iterator lkey;
	for(i=1;i<=c[ROOT].size();i++){
		u=root_son[i];//根的子节点u
		if(u==ROOT) continue;
		if(local_mobile_army[u].size()>0){//有军队从此处进入首都,选取其中剩余时间最小者原地驻扎
			ll temp=now_stationed[u];
			now_stationed[u]-=local_mobile_army[u].size();
			if(check_control(u)){//子树军队已控制疫情
				now_stationed[u]=temp;
				continue;
			}
			now_stationed[u]=temp;
			lkey=local_mobile_army[u].begin();//将此军队从考虑范围中去除
			nkey=nation_mobile_army.find((MB_ARMY){u,*lkey});
			local_mobile_army[u].erase(lkey);
			if(nkey!=nation_mobile_army.end()) nation_mobile_army.erase(nkey);
			now_stationed[u]--;
		}
		else{//此地军队已用完或无军队前来
			if(!check_control(u)){//在此点子树中未控制疫情
				nkey=nation_mobile_army.lower_bound((MB_ARMY){0,fatherlen[u]});//选择剩余时间尽量小的军队驻扎
				if(nkey==nation_mobile_army.end()) return false;
				now_stationed[nkey->ic]--;
				now_stationed[u]++;
				lkey=local_mobile_army[nkey->ic].find(nkey->lt);
				if(lkey!=local_mobile_army[nkey->ic].end()) local_mobile_army[nkey->ic].erase(lkey);
				nation_mobile_army.erase(nkey);
			}
		}
	}
	return true;
}
ll find(ll left,ll right){//在[left,right]内找答案
	if(left==right) return left;
	ll mid=(left+right)>>1;
	if(check_feas(mid)) return find(left,mid);
	return find(mid+1,right);
}
void getfather(ll x){
	ll i;
	#define now c[x][i]
	for(i=0;i<c[x].size();i++){
		if(now.first!=father[x]){
			father[now.first]=x;
			fatherlen[now.first]=now.second;
			getfather(c[x][i].first);
		}
	}
}
bool cmp(ll a,ll b){
	return fatherlen[a]>fatherlen[b];
}
void init(void){
	scanf("%lld",&n);
	ll i;
	ll u,v,w;
	for(i=1;i<n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		c[u].push_back(make_pair(v,w));
		c[v].push_back(make_pair(u,w));
	}
	scanf("%lld",&m);
	for(i=1;i<=m;i++){
		scanf("%lld",&u);
		army_station[i]=u;
		ori_stationed[u]++;
	}
	getfather(ROOT);
	for(i=0;i<c[ROOT].size();i++) root_son[i+1]=c[ROOT][i].first;
	sort(root_son+1,root_son+1+c[ROOT].size(),cmp);
}
int main(){
	freopen("blockade.in","r",stdin);
	freopen("blockade.out","w",stdout);
	init();
	if(m<c[ROOT].size()){//军队总数小于根的子节点数,无法控制
		printf("-1\n");
		return 0;
	}
	printf("%lld\n",find(0,INF));
	return 0;
}