40pts求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+1, K = 16;
int n, m, a[N];
bool vis[N], B[N];
ll f[N][K], g[N][K];
vector<pair<int, int>> e[N];
vector<ll> h[N]; // 剩余时间
void dfs(int u, int fa){
    for(auto [v, w]:e[u]){
        if (v == fa) continue;
        f[v][0] = u;
        g[v][0] = w;
        dfs(v, u);
    }
}
bool check(ll t){
    // 答案 <= t
    //cout << t << '\n';
    memset(B, 0, sizeof B);
    for(int i=1;i<=n;i++) h[i].clear();
    for(int i=1;i<=m;i++){
        ll c = t;
        int u = a[i];
        for(int j=K-1;j>=0;j--){
            if (f[u][j] > 1 && g[u][j] <= c){
                c -= g[u][j];
                u = f[u][j];
            }
        }
        //cout << c << ' ' << g[u][0] << '\n';
        if (f[u][0] == 1 && c >= g[u][0]) h[u].push_back(c-g[u][0]); // 可以到根节点，就需要存入h中，h[x]表示节点x的军队到根节点后剩余时间
        else B[u] = 1; // 不可到根节点，只能阻塞叶子节点到根节点
    }
    //for(int i=1;i<=n;i++) cout << B[i] << ' '; cout << '\n';
    for(auto [i,j]: e[1]) sort(h[i].begin(), h[i].end()); // 排序，以便进行处理
    memset(vis, 0, sizeof vis); // vis表示叶子节点到达的未阻塞区域
    queue<int> q;
    for(int i=2;i<=n;i++)
        if (e[i].size() == 1){
            vis[i] = 1;
            q.push(i); // 已经到达
        }
    while(!q.empty()){
        int u = q.front(); q.pop();
        //cout << u << ' ';
        vis[u] = 1;
        if (B[u] || u==1) continue;
        for(auto[v, w]:e[u]){
            if (vis[v]) continue;
            q.push(v);
        }
    }
    //cout << '\n';
    vector<ll> need, have;
    for(auto [i,_i]:e[1]){
        //for(auto j:h[i]) cout << j << ' '; cout << '\n';
        if (vis[i] && h[i].empty()){ // 不可被 i 的子树驻军
            if (vis[i]) need.push_back(g[i][0]); // 需要驻军的
            continue;
        }
        //cout << ":" << vis[i] << ' ' << B[i] << '\n';
        if (vis[i] && !B[i] && h[i].size()) h[i].pop_back(); // 需要保留一个，因为未被阻塞
        //while(h[i].back() <= 0) h[i].pop_back(); //
        for(auto j:h[i]) have.push_back(j);
    }
    sort(need.begin(), need.end()); // 需要驻军的
    sort(have.begin(), have.end()); // 可移动的
    // len(have) >= len(need), have >= need
    //cout<<t<<'\n';
    //for(auto i:need) cout << i << ' ';cout<<'\n';
    //for(auto i:have) cout << i << ' ';cout<<"\n\n";
    auto it = have.begin();
    for(auto i:need){
        if (it == have.end()) return 0;
        while(*it < i){
            it++;
            if (it == have.end()) return 0;
        }
        it++;
    }
    return 1;
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u, v, w;
        cin>>u>>v>>w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    dfs(1, 0);
    for(int j=1;j<K;j++)
        for(int i=1;i<=n;i++){
            f[i][j] = f[f[i][j-1]][j-1];
            g[i][j] = g[i][j-1] + g[f[i][j-1]][j-1];
        }
    cin>>m;
    if (e[1].size() > m){
        cout << -1;
        return 0;
    }
    for(int i=1;i<=m;i++) cin>>a[i];
    ll l = 0, r = 5e13;
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}