记录编号	129791	评测结果	EWWW
题目名称	加法问题	最终得分	0
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.080 s
提交时间	2014-10-20 21:50:56	内存使用	3.18 MiB

/*
1.军队在没有经过根节点时一定不会向下走
2.军队经过根节点支援时一定在root的亲子上
3.只有空闲的军队才会经过根节点
4.对于T值，只有全都封锁时才向下分
5. 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#define Maxn 50010
#define INF 1e7
#define ROOT 1
using namespace std;
int n,m,x,y,v;	//n为节点数，m为军队数 
vector< pair<int,int> > T[Maxn];	//T树为正树
int army_pos[Maxn]={0}; //第i个城市中的军队个数
int now_army_at[Maxn]={0},nat_army_at[Maxn];
int father[Maxn],fatherlen[Maxn];  //记录i的父亲节点 
int nation_child[Maxn]; //首都的根节点 
struct Man{
	int rootnow,lifttime;
	bool operator<(const Man a)const{
		return lifttime<a.lifttime;
	}
};
multiset<Man> nation_armys;	//首都的军队 
multiset<int> local_armys[Maxn];	//首都子节点的军队，键值为剩余时间 
bool cmp(const int x,const int y){
	return fatherlen[x]<fatherlen[y];
}
void getfather(int root){	//记录父亲节点 
	for(int i=0;i<T[root].size();i++){
		#define now T[root][i]
		father[now.first]=root;
		fatherlen[now.first]=now.second;
		getfather(now.first);
	}
}
void init(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&v);
		if(x>y) swap(x,y);	//保证了首都为根 
		T[x].push_back(make_pair(y,v));	//first是点，second为权 
		T[y].push_back(make_pair(x,v));
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&army_pos[i]);
		nat_army_at[x]++;
	}
	for(int i=0;i<T[ROOT].size();i++){	//安置排序 
		nation_child[i+1]=T[ROOT][i].first;
	}
	getfather(ROOT);
	sort(nation_child+1,nation_child+T[ROOT].size()+1,cmp);
}
bool check_control(int root){	//检查是否已控制 
	if(now_army_at[root]>0) return true;
	if(T[root].size()==1) return false;
	for(int i=0;i<T[root].size();i++){
		if(T[root][i].first==father[root]) continue;
		if(!check_control(T[root][i].first)){
			return false;
		}
	}
	return true;
}
void sigal_up(int root,int lifttime){ //以lifttime的时间尽量吧root向上翻 
	if(fatherlen[root]>lifttime) return;
	if(father[root]==ROOT){	//到达了根 
		nation_armys.insert((Man){root,lifttime-fatherlen[root]});
		local_armys[root].insert(lifttime-fatherlen[root]);
	}
	else{	//正常的向上翻 
		now_army_at[root]--;
		now_army_at[father[root]]++;
		sigal_up(father[root],lifttime-fatherlen[root]);
	}
} 
void up_all(int lifttime){	 //集体向上翻查 
	for(int i=1;i<=n;i++){
		now_army_at[i]=nat_army_at[i];	//初始化 
	}
	for(int i=1;i<=m;i++){
		sigal_up(army_pos[i],lifttime);	//尝试以每一个向上翻 
	}
}
bool OK(int lifttime){
	nation_armys.clear();
	for(int i=0;i<T[ROOT].size();i++) local_armys[i].clear();
	multiset<Man>::iterator nkey;
	multiset<int>::iterator lkey;
	up_all(lifttime);
	for(int i=1;i<=T[ROOT].size();i++){
		int u=nation_child[i];
		if(local_armys[u].size()>0){ 
			int temp=now_army_at[u];
			now_army_at[u]-=local_armys[u].size();
			if(check_control(u)){	//如果可以控制住，跳过
				now_army_at[u]=temp;	// 
				continue;
			}
			now_army_at[u]=temp;
			nkey=nation_armys.lower_bound((Man){0,lifttime});
			if(nkey==nation_armys.end()) return false;
			else nation_armys.erase(nkey);
		}
		else{
			
		}
	}
	return true;
}
int Find(int X,int Y){	//二分T值 
	int L=0,R=INF;
	while(L<=R){
		int Mid=(L+R)>>1;
		if(OK(Mid)) R=Mid-1;
		else L=Mid+1;
	}
	return L;
}
int main(){
	freopen("aplusb.in","r",stdin);
	freopen("aplusb.out","w",stdout);
	init(); 
	printf("%d\n",Find(0,INF));
	return 0;
}