记录编号	465510	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.501 s
提交时间	2017-10-27 10:22:02	内存使用	7.59 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
struct edge{int v,next;long long dis;}e[maxn<<1];
struct poi{int come;long long dis;}res[maxn];//记录已经被保护的城市
struct prc{int city,dis;}unp[maxn];//protect city
bool cmp1(poi x,poi y){return x.dis<y.dis;}
bool cmp2(prc x,prc y){return x.dis<y.dis;}
int n,m,tot,cnt,cct,f[maxn][20],dep[maxn],nps[maxn],pos[maxn],dis[maxn],head[maxn];
bool pro[maxn];//受保护的城市
void dfs(int u){
	dep[u]=dep[f[u][0]]+1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==f[u][0])continue;
		f[v][0]=u,dis[v]=dis[u]+e[i].dis;
		dfs(v);
	}
}
void lcainit(){
	for(int i=1;i<=16;i++)
		for(int j=1;j<=n;j++)
			f[j][i]=f[f[j][i-1]][i-1];
}
void find(int u){//寻找哪些城市没有被保护
	if(!e[head[u]].next)return;
	bool flag=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].v;
		if(v==f[u][0]||pro[v])continue;
		find(v);
		if(!pro[v])flag=0;
	}
	pro[u]=flag;
	return;
}
bool check(long long tim){
	memset(pro,0,sizeof(pro));
	memset(res,0,sizeof(res));
	memcpy(nps,pos,sizeof(pos));
	cnt=0,cct=0;
	for(int i=1;i<=m;i++){//nps[i]:第i个军队现在的位置
		if(dis[nps[i]]>tim){//时间不够回到首都
			long long tmp=dis[nps[i]]-tim;
			for(int j=16;j>=0;j--)
				if(dis[f[nps[i]][j]]>=tmp)nps[i]=f[nps[i]][j];
			pro[nps[i]]=1;
		}
		else{//时间够回到首都
			res[++cnt].dis=tim-dis[nps[i]];
			for(int j=16;j>=0;j--)
				if(dep[f[nps[i]][j]]>1)nps[i]=f[nps[i]][j];
			res[cnt].come=nps[i];
		}
	}
	find(1);
	if(pro[1])return true;
	for(int i=head[1];i;i=e[i].next){
		int v=e[i].v;
		if(!pro[v])unp[++cct].city=v,unp[cct].dis=e[i].dis;
	}
	sort(res+1,res+1+cnt,cmp1);
	sort(unp+1,unp+1+cct,cmp2);
	int j=1;
	for(int i=1;i<=cnt;i++){
		if(!pro[res[i].come]){pro[res[i].come]=1;continue;}
		while(pro[unp[j].city]&&j<=cct)j++;
		if(unp[j].dis<=res[i].dis)pro[unp[j].city]=1,j++;
	}
	for(int i=1;i<=cct;i++)
		if(!pro[unp[i].city])return false;
	return true;
}
int main(){
	freopen("blockade.in","r",stdin);
	freopen("blockade.out","w",stdout);
	scanf("%d",&n);
	int u,v;
	long long w,l=1,r=0,ans=-1;
	for(int i=1;i<n;i++){
		scanf("%d%d%lld",&u,&v,&w);
		tot++,e[tot].v=v,e[tot].next=head[u],e[tot].dis=w,head[u]=tot;
		tot++,e[tot].v=u,e[tot].next=head[v],e[tot].dis=w,head[v]=tot;
		r+=w;
	}
	dfs(1),lcainit();
	scanf("%d",&m);
	for(int i=1;i<=m;i++)scanf("%d",&pos[i]);
	while(l<=r){
		long long mid=(l+r)>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld\n",ans);
	return 0;
}