记录编号	342959	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012]疫情控制	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	1.592 s
提交时间	2016-11-08 20:41:19	内存使用	17.48 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const LL INF=1ll<<30;
const int N=50010,D=17;
int cnt,fir[N],nxt[N*2];
int to[N*2];LL val[N*2];
LL dis[D][N],fa[D][N];
void addedge(register int a,register int b,LL w){
  nxt[++cnt]=fir[a];
  fir[a]=cnt;
  val[cnt]=w;
  to[cnt]=b;
}
int n,m,dep[N];
void Prepare(){
  for(register int k=1;k<=16;k++)
    for(register int i=1;i<=n;i++){
      fa[k][i]=fa[k-1][fa[k-1][i]];
      dis[k][i]=dis[k-1][i]+dis[k-1][fa[k-1][i]];
    }
}
void DFS(register int x){
  for(register int i=fir[x];i;i=nxt[i])
    if(to[i]!=fa[0][x]){
      fa[0][to[i]]=x;
      dep[to[i]]=dep[x]+1;
      dis[0][to[i]]=val[i];
      DFS(to[i]);
    }
}
int dp[N],st[N];
vector<LL>v[N];
void DP(register int x){
  if(dep[x]>1)
    dp[x]=v[x].size();
  else dp[x]=0;
  bool tmp=true,flag=false;
  for(register int i=fir[x];i;i=nxt[i])
    if(to[i]!=fa[0][x]){
      DP(to[i]);
      tmp&=dp[to[i]];
      flag=true;
    }
  dp[x]|=tmp&flag;
}
int ca,cb,p[N];
LL a[N],b[N],c[N];
bool Check(LL mid){
  for(register int i=1;i<=n;i++)
    v[i].clear();
  for(register int i=1;i<=m;i++){
    LL tmp=mid;register int x=st[i];
    for(register int k=16;k>=0;k--)
      if(dis[k][x]<=tmp){
      	if(fa[k][x]<=1)continue;
	tmp-=dis[k][x];
	x=fa[k][x];
      }
    v[x].push_back(tmp);
  }
  DP(1);ca=cb=0;
  for(register int i=fir[1],y;i;i=nxt[i]){
    register int sz=v[y=to[i]].size(),z=0;
    if(!dp[y])b[++cb]=val[i],z=cb;
    for(register int j=0;j<sz;j++){
      a[++ca]=v[y][j]-val[i];
      c[ca]=z;
    }
  }
  memset(p,0,sizeof(p));
  for(register int i=1;i<=ca;i++){
    if(!p[c[i]])p[c[i]]=i;
    else if(a[p[c[i]]]>a[i])
      p[c[i]]=i;
  }
  for(register int i=1;i<=cb;i++)
    if(p[i]&&b[i]>a[p[i]]){
      b[i]=a[p[i]]=INF;
    }
  sort(a+1,a+ca+1);while(a[ca]==INF)ca--;
  sort(b+1,b+cb+1);while(b[cb]==INF)cb--;
  for(register int i=1,j=1;i<=ca;i++){
    if(a[i]>=b[j])j++;
    if(j>cb)return true;
  }
  return false;
}


LL l,r,mid,w;
int main(){
  freopen("blockade.in","r",stdin);
  freopen("blockade.out","w",stdout);
  scanf("%d",&n);
  for(register int i=1,a,b;i<n;i++){
    scanf("%d%d%lld",&a,&b,&w);
    addedge(a,b,w);
    addedge(b,a,w);
  }DFS(1);Prepare();
  scanf("%d",&m);
  for(register int i=1;i<=m;i++)
    scanf("%d",&st[i]);
  l=0;r=INF;
  while(l<=r){
    mid=(l+r)>>1;
    if(Check(mid))r=mid-1;
    else l=mid+1;
  }
  if(l>INF)l=-1;
  printf("%lld\n",l);
  return 0;
}