思路与算法

对完成时间T二分。以首都为根预处理父亲、到根距离、第一层分支与倍增祖先。无法在T内到根的军队上移到仍可到达的最高非根结点，在那里设检查点不劣；倒序计算各分支是否全部被封锁。能够到根的军队记录到根后剩余时间r以及原分支。尚未被封锁的每个根孩子需要一支军队：来自本分支的军队可以直接留下，不要求再从根走回来；来自其他分支的军队需满足r不小于根边长度。按r递增处理，若本分支仍待守则直接守本分支，否则守根边最短且可达的待守分支。若根的分支数超过军队数立即无解；否则两倍所有边长之和足以让所有军队任意重新分配。二分包含T=0。

正确性说明

向根上移检查点只会扩大它覆盖的根叶路径集合，因此不能到根的军队停在最高可达非根点是支配选择。剩余需求恰为未封锁的根分支，各需求互不共享军队。对剩余时间最少的一支军队，如果它的原分支待守，任意可行方案中守原分支的另一军队可以与它交换任务：另一军队剩余时间不小，能完成它本来能到达的异分支；本支直接驻守总是可行。若原分支已守，选择最短可达根边同样可与原来负责该分支的较强军队交换。因此递增贪心充要地判断可行性。可行性随T不减，二分得最短时间。

复杂度

预处理含邻接表初始化、树遍历与倍增表为O(n log n)时间、O(n log n+m)空间。每次判定O((n+m)log n+m log m)，包括标记数组清空、军队排序和有序集合初始化；总时间再乘O(log W)，W为二倍边长和。所有距离和阈值使用64位整数。

易错点

首都不能设检查点；叶子未被标记时不能因“没有未覆盖孩子”而视为已守。本分支驻军与跨根调动的可达条件不同。允许多支军队同城，也允许原本已经封锁全部路径而答案为0。根分支多于军队时不是简单加大时间就能解决。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    vector<vector<pair<int, ll>>> g(n);
    ll sum = 0;
    for (int i = 1, u, v; i < n; i++) {
        ll w;
        cin >> u >> v >> w;
        --u;
        --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
        sum += w;
    }
    int m;
    cin >> m;
    vector<int> a(m);
    for (int &v : a) {
        cin >> v;
        --v;
    }
    if ((int)g[0].size() > m) {
        cout << -1 << '\n';
        return 0;
    }
    const int LOG = 16;
    vector<array<int, LOG>> up(n);
    vector<ll> d(n), firstw(n);
    vector<int> ord(1, 0), branch(n), par(n, -1);
    for (size_t k = 0; k < ord.size(); k++) {
        int u = ord[k];
        for (auto e : g[u])
            if (e.first != par[u]) {
                int v = e.first;
                par[v] = u;
                d[v] = d[u] + e.second;
                branch[v] = u ? branch[u] : v;
                firstw[v] = u ? firstw[u] : e.second;
                up[v][0] = u;
                for (int j = 1; j < LOG; j++)
                    up[v][j] = up[up[v][j - 1]][j - 1];
                ord.push_back(v);
            }
    }
    auto ok = [&](ll time) {
        vector<unsigned char> cover(n);
        vector<pair<ll, int>> mobile;
        for (int u : a) {
            if (d[u] <= time) {
                mobile.push_back({time - d[u], branch[u]});
                continue;
            }
            int v = u;
            for (int j = LOG - 1; j >= 0; j--) {
                int w = up[v][j];
                if (w && d[u] - d[w] <= time)
                    v = w;
            }
            cover[v] = 1;
        }
        for (int k = n - 1; k > 0; k--) {
            int u = ord[k];
            if (!cover[u]) {
                bool all = true, child = false;
                for (auto e : g[u])
                    if (e.first != par[u]) {
                        child = true;
                        if (!cover[e.first])
                            all = false;
                    }
                cover[u] = all && child;
            }
        }
        set<pair<ll, int>> need;
        for (auto e : g[0])
            if (!cover[e.first])
                need.insert({e.second, e.first});
        sort(mobile.begin(), mobile.end());
        for (auto a : mobile) {
            int b = a.second;
            auto it = need.find({firstw[b], b});
            if (it != need.end())
                need.erase(it);
            else if (!need.empty() && need.begin()->first <= a.first)
                need.erase(need.begin());
        }
        return need.empty();
    };
    ll lo = -1, hi = 2 * sum;
    while (hi - lo > 1) {
        ll mid = lo + (hi - lo) / 2;
        if (ok(mid))
            hi = mid;
        else
            lo = mid;
    }
    cout << hi << '\n';
}