记录编号	193837	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.751 s
提交时间	2015-10-15 16:46:32	内存使用	20.64 MiB

#include<cstdio>
#include<deque>
#include<set>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZEN=50010,maxn=0x7fffffff/2;
typedef long long LL;
//二分时间，处理出军队到各点的时间
int n,m;
class miku
{
public:
	int to,lo;
	miku(){}
	miku(int b,int c)
	{
		to=b,lo=c;
	}
};
deque<miku> s[50010];
multiset<LL> c[SIZEN];
multiset<LL> G;
int f[50010]={0};
int w[50010]={0};
int se[50010]={0},cut[SIZEN];//驻军地点
bool arr[50010];
bool P[SIZEN];
LL ma;
void add(int fr,int to,int lo)
{
	s[fr].push_back(miku(to,lo));
	s[to].push_back(miku(fr,lo));
}
void dfs(int x,int fa)
{
	for(int i=0;i<s[x].size();i++)
	{
		if(s[x][i].to==fa) continue;
		f[s[x][i].to]=x;w[s[x][i].to]=s[x][i].lo;
		dfs(s[x][i].to,x);
	}
}
void climb(int x,int t)
{
	int tem=se[x];
	while(tem!=1&&t>=w[tem])
	{
		if(f[tem]==1) c[tem].insert(t-w[tem]);
		t-=w[tem];
		tem=f[tem];
	}
	if(tem!=1) arr[tem]=1;
	else G.insert(t);
}
bool check_con(int x)
{
	if(arr[x]==1) return 1;
	if(s[x].size()==1) return 0;
	for(int i=0;i<s[x].size();i++)
	{
		int v=s[x][i].to;
		if(v==f[x]) continue;
		if(!check_con(v)) return 0;
	}
	arr[x]=1;return 1;
}
bool check(int t)
{
	G.clear();
	for(int i=0;i<s[1].size();i++) c[s[1][i].to].clear();
	memset(arr,0,sizeof(arr));
	for(int i=1;i<=m;i++) climb(i,t);
	multiset<LL>::iterator key,it;
	//cout<<"G:";for(key=G.begin();key!=G.end();key++) cout<<*key<<" ";
	//cout<<endl;
	for(int i=0;i<s[1].size();i++)
	{
		int v=s[1][i].to;
		if(c[v].size()>0)
		{
			if(check_con(v)) continue;
			arr[v]=1;
			key=c[v].begin();
			it=G.lower_bound(w[v]);
			//cout<<*it<<" "<<*key<<" "<<v<<" "<<w[v]<<endl;
			//cout<<"G:";for(key=G.begin();key!=G.end();key++) cout<<*key<<" ";
			//cout<<endl;
			if(G.find(*key)!=G.end()&&(it==G.end()||*key<*it)) G.erase(G.find(*key));
			else G.erase(it);
		}
	}
	for(int i=0;i<s[1].size();i++)
	{
		int v=s[1][i].to;
		if(check_con(v)) continue;
		//cout<<v<<" "<<w[v]<<endl;
		//cout<<"G:";for(key=G.begin();key!=G.end();key++) cout<<*key<<" ";
		//cout<<endl;
		key=G.lower_bound(w[v]);
		if(key==G.end()) return 0;
		G.erase(key);
	}
	return 1;
}
void work()
{
	LL l=0,r=ma;
	scanf("%d",&m);
	for(int i=1;i<=m;i++) {scanf("%d",&se[i]);P[se[i]]=1;}
	//cout<<P[1]<<endl;
	if(m<s[1].size()) {printf("-1");return;}
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
		//cout<<mid<<endl;
	}
	printf("%d",r);
}
int main()
{
	freopen("blockade.in","r",stdin);
	freopen("blockade.out","w",stdout);
	scanf("%d",&n);
	int fr,to,lo;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&fr,&to,&lo);
		add(fr,to,lo);ma+=lo;
	}
	dfs(1,0);
	//cout<<ma<<endl;
	//for(int i=0;i<s[1].size();i++) cout<<s[1][i].to<<" "<<w[s[1][i].to]<<endl;
	//cout<<w[1752]<<endl;
	work();
	return 0;
}