做法：倍增+二分+贪心

思路：

  • 1.类似于lca的方法，倍增预处理出fa父亲节点和depth到父亲节点的长度数组。
  • 2.二分答案。
  • 3.对于每个当前的mid，把每个军队上提到能够达到的最高位置（最高上提到根节点的子节点）。
  • 4.对于可以上提到根节点的子节点，再经过根节点后还能行走的军队，存入rest_army数组中，同时求出根每个子节点空闲军队走到根节点后剩余行程最小的编号（restnum和restmin）。
  • 5.判断根的子节点的空隙情况，存到gap数组中。
  • 6.贪心。对于rest_army和gap数组进行从大到小排序。

代码

// Problem: 疫情控制
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/16565
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=50010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m,ans;
struct edge{
    int to,cost;
};
vector<edge> g[N];
int depth[N][20],fa[N][20],lg[N],army[N];
bool stay[N],st[N];
int restnum[N],restmin[N];
int restarmy_num,gap_num;
struct node{
    int id;
    int rest;
}rest_army[N],gap[N];

bool cmp(node a,node b){
    return a.rest>b.rest;
}

void init(){
    //log2(i)+1
    for(int i=1;i<=n;i++){
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
}

void dfs(int u,int father,int dep){
    depth[u][0]=dep;
    fa[u][0]=father;
    // 2^i祖先为2^i-1级祖先的2^i-1级祖先
    for(int i=1;i<=17;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
        depth[u][i]=depth[u][i-1]+depth[fa[u][i-1]][i-1];
    }
    for(auto x:g[u]){
        int v=x.to,w=x.cost;
        if(v==father) continue;
        dfs(v,u,w);
    }
}

void clear(){
    restarmy_num = 0;
    gap_num = 0;
    mst(st,0);
    mst(stay,0);
    mst(restnum,0);
}

bool dfs2(int u,int fa){
    if(stay[u]) return 1;
    bool pson=0,no_gap=1;
    for(auto x:g[u]){
        int v=x.to,w=x.cost;
        if(v==fa) continue;
        pson=1;
        if(!dfs2(v,u)){
            no_gap=0;
            if(u==1) gap[++gap_num]={v,w};
            else return 0;
        }
    }
    if(!pson) return 0;
    else return no_gap;
}

bool check(int mid){
    clear();
    for(int i=1;i<=m;i++){
        int u=army[i],dis=0;
        for(int j=lg[u];~j;j--){
            if(fa[u][j]>1&&dis+depth[u][j]<=mid){ //向上走
                dis+=depth[u][j];
                u=fa[u][j];
            }
        }

        if(fa[u][0]==1&&dis+depth[u][0]<=mid){
            rest_army[++restarmy_num]={i,mid-dis-depth[u][0]};
            if(!restnum[u]||restmin[u]>rest_army[restarmy_num].rest){
                restnum[u]=i;
                restmin[u]=rest_army[restarmy_num].rest;
            }
        }
        else stay[u]=1;
    }

    if(dfs2(1,0)) return 1;
    sort(rest_army + 1, rest_army + restarmy_num + 1, cmp);
    sort(gap + 1, gap + gap_num + 1, cmp);

    st[0]=1;
    int now=1;
    for(int i=1;i<=gap_num;i++){
        if(!st[restnum[gap[i].id]]){
            st[restnum[gap[i].id]]=1;
            continue;
        }
        while(now<=restarmy_num && (st[rest_army[now].id] || rest_army[now].rest < gap[i].rest)) now++;
        if(now>restarmy_num) return 0;
        st[rest_army[now].id]=1;
    }
    return 1;
}

void solve(){
    cin>>n;
    init();
    int l=0,r=0;
    for(int i=0;i<n-1;i++){
        int x,y,w;cin>>x>>y>>w;
        g[x].push_back({y,w});
        g[y].push_back({x,w});
        r+=w;
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>army[i];
    }
    if(m<g[1].size()){
        cout<<"-1\n";
        return;
    }
    dfs(1,0,0);
    int ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}