NOIP 2012 疫情控制

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50000+5;
int n;
int m;
int st[N];
struct node{
    int nxt,to;
    ll val;
}e[2*N];
int hd[N],cnt;
ll l,r;
bool son[N];
void add(int x,int y,ll z){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;
    e[cnt].val=z;
    hd[x]=cnt;
}
int fa[N][22];
ll dis[N][22];
ll ans=-1;
bool exi[N];
bool tmp[N];

void dfs(int x){
    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa[x][0]) continue;
        fa[y][0]=x;
        dis[y][0]=e[i].val;
        if(x==1) son[y]=1;
        dfs(y);
    }
}
void dfs2(int x){
    if(exi[x]) return;
    bool fl=true;
    bool has=false;
    for(int i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa[x][0]) continue;
        has=true;
        if(!exi[y]){
            dfs2(y);
            if(!exi[y]) fl=false;
        }
    }
    if(!has) fl=false;
    if(fl) exi[x]=1;
}
struct po{
    int pos;
    ll re;
};//in the son of root
bool cmp(po a,po b){
    return a.re<b.re;
}

vector<po>mem;
multiset<ll>rt;
multiset<ll>::iterator it;

bool che(ll mid){
    
    //cout<<endl<<"bug "<<mid<<endl;
    bool orz1=true;
    bool orz2=true;
    
    memset(exi,0,sizeof exi);
    mem.clear();
    rt.clear();
    
    for(int i=1;i<=m;i++){
        int to=st[i];
        ll has=0;
        for(int j=19;j>=0;j--){
            if(fa[to][j]&&fa[to][j]!=1&&has+dis[to][j]<=mid){
                has+=dis[to][j];
                to=fa[to][j];//1.倍增的顺序不能反了！！ 
            }
        }
        
        //cout<<i<<" st "<<st[i]<<" : "<<to<<" "<<has<<endl;
        
        if(son[to]){
            po ko;
            ko.pos=to,ko.re=mid-has;
            mem.push_back(ko);
        }
        else{//warning !! : no son of tree exi[] is true
            exi[to]=1;
        }
    }
    
    dfs2(1);
   
    sort(mem.begin(),mem.end(),cmp);
    
    memcpy(tmp,exi,sizeof exi);
    
    for(int i=0;i<mem.size();i++){
        po x=mem[i];
        if(!exi[x.pos]){
            exi[x.pos]=1;
        }
        else{
            x.re-=dis[x.pos][0];
            if(x.re>0){
                rt.insert(x.re);
            }
        }
    }
    
    for(int i=hd[1];i;i=e[i].nxt){
        int y=e[i].to;
        if(!exi[y]){
            it=rt.lower_bound(e[i].val);
            if(it==rt.end()) {
            orz1=false;break;}
            
            rt.erase(it);
        }
    }
    
    
    
    if(orz1) return true;
    
    
    
    rt.clear();
    
    memcpy(exi,tmp,sizeof tmp);
    
    for(int i=0;i<mem.size();i++){
        po x=mem[i];
        x.re-=dis[x.pos][0];
        //cout<<x.pos<<" "<<x.re<<endl;
        if(x.re>0){
            rt.insert(x.re);
        }
        else exi[x.pos]=1;
    }
    
    for(int i=hd[1];i;i=e[i].nxt){
        int y=e[i].to;
        if(!exi[y]){
            //cout<<" go "<<y<<endl;
            it=rt.lower_bound(e[i].val);
            if(it==rt.end()){
            orz2=false;break;}
            
            rt.erase(it);
        }
    }
    
    if(orz2) return true;
    
    return false;
}
int main()
{
    scanf("%d",&n);
    int x,y;
    ll z;
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%lld",&x,&y,&z);
        add(x,y,z);add(y,x,z);
        r+=z;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d",&st[i]);
    
    dfs(1);
    //cout<<" on the tree"<<endl;
    /*for(int i=1;i<=n;i++){
        cout<<i<<" : "<<fa[i][0]<<" "<<dis[i][0]<<endl;
    }*/
    for(int j=1;j<=19;j++){
        for(int i=1;i<=n;i++){
            fa[i][j]=fa[fa[i][j-1]][j-1];
            dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
        }
    }
    l=0;
    
    //printf("ahhahahaah %d\n",che(30));
    
    while(l<=r){
        
        ll mid=(l+r)>>1;
        
        if(che(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}