疫情控制

形式化题目

给定一棵 $n$ 个点、以 $1$ 为根的树，边权 $w > 0$ ，叶子点称为边境城市。要在若干非根点上放检查点，使每条「根 → 叶子」路径都至少经过一个检查点（边境城市也可以放）。

现有 $m$ 支军队，各自驻扎在给定城市，可以沿道路移动到任意城市，放下恰好一个检查点，且不能放在首都；走一条边耗时等于边权，各军同时行动。求让全部路径都被看住的最少小时数（各军耗时的最大值）；做不到输出 $-1$ 。约束： $2 \leqslant m \leqslant n \leqslant 50000$ ， $0 < w < 10^9$ 。

样例：两支军队都驻在城市 2，答案 $3$ 。下图是样例的树（边上为权值）：

graph TD
    A["1 · 首都<br/>不可建检查点"] -->|"w=1"| B["2 · 边境<br/>驻扎 2 支军队"]
    A -->|"w=2"| C["3"]
    C -->|"w=3"| D["4 · 边境"]

一条边境路径是 $1 \to 2$ ，另一条是 $1 \to 3 \to 4$ ，因此至少要在 2 和 3（或 4）各放一个检查点。一支军队原地在 2 建点（0 小时）；另一支走 $2 \to 1$ （1 小时）再 $1 \to 3$ （2 小时）在 3 建点，两军同时行动，总时间 $3$ 。若想把检查点建在 4，需要 $1 + 2 + 3 = 6$ 小时，更差。

正解

思路

朴素想法：卡在"时间未知"

任意一支驻在 $s$ 的军队若落在点 $x$ ，就看住整棵子树 $\mathrm{sub}(x)$ 。朴素做法要么枚举检查点集合、要么枚举时间再模拟，但检查点组合是指数级的， $n = 50000$ 完全不可行。换角度：答案是各军耗时的最大值，典型的「最小化最大值」——先二分答案 $T$ ，把问题变成判定「 $T$ 小时内能否控制疫情」。判定可以贪心，难点全在判定里落点的结构。

关键观察一：有效落点只有两类

军队可以满树乱走，但对任意落点 $x \neq 1$ ，记 $a$ 为 $s$ 到根路径上与 $x$ 分叉前的最后一个点（ $a$ 是 $s$ 的祖先， $a = \mathrm{lca}(s, x)$ ）：

走到 $x$ 的耗时是 $\mathrm{depth}[s] + \mathrm{depth}[x] - 2\,\mathrm{depth}[a]$ ，而停在 $a$ 只花 $\mathrm{depth}[s] - \mathrm{depth}[a]$ ，更省时间；
覆盖上 $a$ 看住 $\mathrm{sub}(a) \supseteq \mathrm{sub}(x)$ ，只多不少。

所以只要 $a \neq 1$ ，停在 $a$ 严格不劣于走到 $x$ 。 $a = 1$ 时不能建点，唯一的出路是穿过首都继续下到某个根儿子 $c$ （下得更深只会更贵、覆盖更窄，落到 $c$ 即可）。于是每支军队的有效选择恰好两类：

落在自己到根路径上的某个祖先（含自己的根儿子）；
穿过首都，落在任意根儿子 $c$ ，耗时 $\mathrm{depth}[s] + w_c$ 。

关键观察二：走不到首都的军队别无选择

记 $\mathrm{depth}[s]$ 为 $s$ 到根的距离。若 $\mathrm{depth}[s] > T$ ，军队连首都都到不了，只能选第 1 类。耗时不超过 $T$ 的祖先中最高的那个 $a$ （即 $\mathrm{depth}[s] - \mathrm{depth}[a] \leqslant T$ 里 $\mathrm{depth}[a]$ 最小者）覆盖 $\mathrm{sub}(a)$ 最大，选它只强不弱——这类军队的落点是确定的，先把它们全部落好，再做覆盖统计：自根向下标记「根到此是否已有检查点」，自底向上找「子树里还有没有裸叶子（从根到它无检查点的叶子）」。

关键观察三：需求与预备队的匹配

覆盖统计后，每个还含裸叶子的根儿子子树必须补一个检查点。为什么粒度正好是「根儿子子树」？因为这类子树里的裸叶子，靠已有落点已经补不齐了，而一支军队落在这个根儿子 $c$ 上，恰好一次看住整棵 $\mathrm{sub}(c)$ ；落到它深处反而更贵、看住的更少。于是问题变成：

每个需求（根儿子 $c$ ，代价 $w_c$ ）配一支「能到首都的军队」，每支军队恰好服务一个需求。

能到首都的军队（ $\mathrm{depth}[s] \leqslant T$ ）是预备队，两种用法：

免费：落在自己的根儿子 $c_0$ 上——不折返，耗时 $\mathrm{depth}[s] - w_{c_0} \leqslant \mathrm{depth}[s] \leqslant T$ 恒成立；
折返：穿过首都落到任意根儿子 $c$ ，耗时 $\mathrm{depth}[s] + w_c \leqslant T$ ，等价于剩余时间 $r = T - \mathrm{depth}[s] \geqslant w_c$ 。

匹配贪心：需求按 $w_c$ 从大到小处理。第 1 优先用「属于该子树、还没被用掉的预备队」里剩余时间最小的一支（免费）；没有就从剩余时间 $r \geqslant w_c$ 的预备队里挑 $r$ 最小的一支折返过去。交换论证：

免费步：若某可行方案没让这支最小 $r$ 的本组预备队 $X$ 落在 $c$ ，而是让别的预备队 $Y$ 落 $c$ （必有 $r_Y \geqslant w_c$ ）， $X$ 落在别处的需求 $c'$ （ $w' \leqslant w_c$ ，故 $r_X \geqslant w'$ ）。交换成 $X$ 落 $c$ （免费）、 $Y$ 落 $c'$ ： $r_Y \geqslant w_c \geqslant w'$ 仍成立，方案照旧可行；挑 $r$ 最小保证被换走的 $X$ 不会带走大额剩余时间。
折返步：设贪心挑了满足 $r \geqslant w_c$ 中最小的 $M$ 。可行方案里落 $c$ 的是 $Y$ （ $r_Y \geqslant w_c$ ，此时未被用），而 $M$ 在该方案里落在更小的需求 $c'$ （ $w' \leqslant w_c$ ； $M$ 闲置则更简单）。交换成 $M$ 落 $c$ 、 $Y$ 落 $c'$ ： $r_Y \geqslant w_c \geqslant w'$ 仍可行。

归纳下去：只要存在方案，贪心每步之后仍有方案，故贪心成功 $\Leftrightarrow$ 判定可行。

两个实现细节

「走不到首都的军队跳到最高可达祖先」用倍增：祖先链上 $\mathrm{depth}$ 单调递减，从 $2^{k}$ 大的跳开始，只要跳点的 $\mathrm{depth} \geqslant \mathrm{depth}[s] - T$ 就跳， $O(\log n)$ 一支。
「剩余时间 $r \geqslant w_c$ 的最小 $r$ 」即「 $\mathrm{depth} \leqslant T - w_c$ 的最大 $\mathrm{depth}$ 」：军队按 $\mathrm{depth}$ 升序编号后是一个前缀，用树状数组维护可用军队的前缀计数，取「第 $q$ 个可用者」即区间内最后一个可用者，增删都是 $O(\log n)$ 。

另外，每支军队最多盖住一个根儿子子树，所以根儿子数大于 $m$ 时直接输出 $-1$ ；否则取上界 $\max \mathrm{depth} + \max w_c$ （此时全员预备队、剩余时间处处够用）二分。

样例推演

下表是 $T = 3$ 的判定过程（两军同驻城市 2， $\mathrm{depth} = 1$ ，无「走不到首都」的军队，故需求是两个都没被覆盖的根儿子）：

处理顺序	需求（根儿子 / 边权）	裸叶子	挑选的预备队	行动与耗时	落点看住
1	3 / 2	4	折返步： $r \geqslant 2$ 中最小者（ $r = 2$ ）	$2 \to 1 \to 3$ ， $1 + 2 = 3 \leqslant 3$	$\{3, 4\}$
2	2 / 1	2	免费步：属于 2 的剩余预备队	原地不动， $1 - 1 = 0$	$\{2\}$

表格每行是一个需求：先按边权从大到小处理，列出裸叶子、贪心选中的军队、实际耗时与最终覆盖范围。两行做完所有裸叶子都有检查点，判定可行。而 $T = 2$ 时需求相同，两支预备队剩余都只有 $1 < 2$ ，需求 3 无人能落，折返步失败——判定不可行。二分即得答案 $3$ ，与样例一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:30
 * update_at: 2026-10-10 13:30
 */

// 疫情控制：二分答案 + 贪心 + 树状数组。
// 判定 limit 小时内能否让每条「首都→边境」路径上都有检查点：
// 走不到首都的军队就近跳到最高可达祖先；能到首都的军队当预备队，
// 优先补自己子树的需求（免费），不够再花时间折返。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

typedef long long ll;

const int MAXN = 50005;
const int MAXLOG = 18; // 2^17 > 50000

struct Ed { // 邻接表里的一条边
    int to;
    ll w;
};

int n, m, lg;
vector<vector<Ed> > adj;      // 按输入顺序建邻接表
vector<int> children[MAXN];   // 先根序下的孩子表
int parent[MAXN];
ll depth[MAXN];  // 各城市到首都的距离
ll pw[MAXN];     // 到父边的权值
int order[MAXN]; // 栈式 DFS 的先根序
int up[MAXLOG][MAXN]; // 倍增表
int origin[MAXN];     // 军队属于哪个根儿子的子树，-1 表示没有
int armies[MAXN];
ll dSorted[MAXN]; // 能到首都的判定：按到根距离排序的军队深度
int tops[MAXN], topCnt;    // 根的儿子，按边权从大到小
int tid[MAXN];             // 根儿子 -> tops 下标
int cp[MAXN], cov[MAXN], unc[MAXN];
int bitT[MAXN];            // 树状数组（容量 f）
int bitLen;
int gused[MAXN];           // 本轮军队是否已用
int curs[MAXN];            // 每个根儿子的「可动上界」缓存
int markArr[MAXN];
int needsArr[MAXN];
vector<vector<int> > groups; // 每个根儿子的军队（按深度升序）
vector<vector<ll> > gd;

int findUpperLL(const ll *arr, int len, ll v) { // 第一个 > v 的下标（等于 bisect_right）
    int lo = 0, hi = len;
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (arr[mid] <= v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int findUpperVec(const vector<ll> &arr, ll v) { // 同上，作用于升序 vector
    int lo = 0, hi = arr.size();
    while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (arr[mid] <= v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

void bitAdd(int i, int delta) { // 0-based 单点增减
    i += 1;
    while (i <= bitLen) {
        bitT[i] += delta;
        i += i & -i;
    }
}

int bitSum(int i) { // 前缀和：下标 [0, i]，i 为 -1 时得 0
    int s = 0;
    i += 1;
    while (i > 0) {
        s += bitT[i];
        i -= i & -i;
    }
    return s;
}

int bitKth(int q) { // 树上倍增找第 q 个 1 的 0-based 下标
    int idx = 0, bit = 1;
    while (bit * 2 <= bitLen + 1) bit *= 2;
    while (bit) {
        int nxt = idx + bit;
        if (nxt <= bitLen && bitT[nxt] < q) {
            q -= bitT[nxt];
            idx = nxt;
        }
        bit >>= 1;
    }
    return idx;
}

bool cmpDepth(int x, int y) { return depth[x] < depth[y]; }
bool cmpPwDesc(int x, int y) { return pw[x] > pw[y]; }

bool feasible(ll limit) {
    int f = findUpperLL(dSorted, m, limit); // 能走到首都的军队数
    int markCnt = 0;
    for (int idx = f; idx < m; ++idx) { // 走不到首都的：原地走到最高可达祖先
        int s = armies[idx];
        ll th = depth[s] - limit; // 祖先距离下限，恒大于 0，跳不进根
        int x = s;
        for (int k = lg - 1; k >= 0; --k) {
            int y = up[k][x];
            if (depth[y] >= th) x = y;
        }
        cp[x] = 1;
        markArr[markCnt] = x;
        ++markCnt;
    }

    cov[0] = cp[0];
    for (int i = 1; i < n; ++i) { // 检查点沿先根序向下渗透
        int x = order[i];
        cov[x] = cp[x] ? 1 : cov[parent[x]];
    }
    for (int i = n - 1; i >= 0; --i) { // 自底向上找「还有裸叶子」的子树
        int x = order[i];
        if (cov[x]) unc[x] = 0;
        else if (!children[x].empty()) {
            unc[x] = 0;
            for (int j = 0; j < (int)children[x].size(); ++j) {
                if (unc[children[x][j]]) { unc[x] = 1; break; }
            }
        } else unc[x] = 1; // 叶子且从根到此无检查点
    }
    int needCnt = 0;
    for (int i = 0; i < topCnt; ++i) {
        int c = tops[i];
        if (unc[c]) {
            needsArr[needCnt] = c;
            ++needCnt;
            if (needCnt > f) break; // 需求比预备队还多，直接判负
        }
    }

    bool ok = needCnt <= f;
    if (ok) {
        bitLen = f;
        bitT[0] = 0;
        for (int i = 1; i <= f; ++i) bitT[i] = i & -i; // 建容量 f 的全 1 树状数组
        for (int i = 0; i < m; ++i) gused[i] = 0;
        for (int i = 0; i < topCnt; ++i) curs[i] = -2;
        for (int i = 0; i < needCnt; ++i) {
            int c = needsArr[i];
            int gtid = tid[c];
            if (!groups[gtid].empty()) { // 优先用「自己子树」的军队免费落在 c
                int cur = curs[gtid];
                if (cur == -2) { // 该组还没算过可动上界
                    cur = findUpperVec(gd[gtid], limit) - 1;
                    curs[gtid] = cur;
                }
                while (cur >= 0 && gused[groups[gtid][cur]]) cur -= 1;
                curs[gtid] = cur;
                if (cur >= 0) {
                    int idx = groups[gtid][cur];
                    gused[idx] = 1;
                    bitAdd(idx, -1);
                    continue;
                }
            }
            // 否则从首都折返下到 c：挑剩余时间够的最弱一支
            int pos = findUpperLL(dSorted, m, limit - pw[c]) - 1;
            int q = bitSum(pos);
            if (q == 0) { ok = false; break; }
            int idx = bitKth(q);
            gused[idx] = 1;
            bitAdd(idx, -1);
        }
    }

    for (int i = 0; i < markCnt; ++i) cp[markArr[i]] = 0; // 清掉本轮检查点，供下次复用
    return ok;
}

int main() {
    if (scanf("%d", &n) != 1) return 0; // 空输入安全返回
    adj.assign(n, vector<Ed>());
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        ll w;
        scanf("%d %d %lld", &u, &v, &w);
        u -= 1;
        v -= 1;
        Ed e;
        e.to = v; e.w = w;
        adj[u].push_back(e);
        e.to = u;
        adj[v].push_back(e);
    }
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &armies[i]);
        armies[i] -= 1;
    }

    // 从根出发的迭代 DFS：一次拿到父指针、到根距离、子表和先根序
    for (int i = 0; i < n; ++i) parent[i] = -1;
    parent[0] = 0; // 根的父亲记成自己，回头时不会被当成孩子
    vector<int> stk;
    stk.push_back(0);
    int ordCnt = 0;
    while (!stk.empty()) {
        int x = stk.back();
        stk.pop_back();
        order[ordCnt++] = x;
        for (int j = 0; j < (int)adj[x].size(); ++j) {
            int y = adj[x][j].to;
            ll w = adj[x][j].w;
            if (y == parent[x]) continue;
            parent[y] = x;
            depth[y] = depth[x] + w;
            pw[y] = w;
            children[x].push_back(y);
            stk.push_back(y);
        }
    }

    // 倍增表：判定时让到不了根的军队跳到 limit 内最高的祖先
    lg = 0;
    while ((1 << lg) <= n - 1) ++lg; // lg = (n-1).bit_length()
    if (lg > MAXLOG) lg = MAXLOG;
    for (int x = 0; x < n; ++x) up[0][x] = parent[x];
    for (int k = 1; k < lg; ++k) {
        for (int x = 0; x < n; ++x) up[k][x] = up[k - 1][up[k - 1][x]];
    }

    // 每支军队属于哪个根儿子的子树（根的儿子上不算）
    for (int i = 0; i < n; ++i) origin[i] = -1;
    for (int i = 1; i < n; ++i) {
        int x = order[i];
        origin[x] = (parent[x] == 0) ? x : origin[parent[x]];
    }

    sort(armies, armies + m, cmpDepth); // 按到根距离升序
    for (int i = 0; i < m; ++i) dSorted[i] = depth[armies[i]];

    topCnt = 0;
    for (int i = 0; i < (int)children[0].size(); ++i) tops[topCnt++] = children[0][i];
    stable_sort(tops, tops + topCnt, cmpPwDesc); // 需求按边权从大到小
    for (int i = 0; i < topCnt; ++i) tid[tops[i]] = i;
    groups.assign(topCnt, vector<int>());
    gd.assign(topCnt, vector<ll>());
    for (int idx = 0; idx < m; ++idx) {
        int c = origin[armies[idx]];
        if (c != -1) groups[tid[c]].push_back(idx);
    }
    for (int i = 0; i < topCnt; ++i) {
        for (int j = 0; j < (int)groups[i].size(); ++j) gd[i].push_back(depth[armies[groups[i][j]]]);
    }
    for (int i = 0; i < n; ++i) { cp[i] = 0; cov[i] = 0; unc[i] = 0; }

    // 每支军队最多盖住一个根儿子子树，m 支盖不齐 k 个子树时无解
    if (topCnt > m) {
        printf("-1\n");
        return 0;
    }
    ll high = 0;
    ll mxPw = 0;
    for (int i = 0; i < n; ++i) if (depth[i] > high) high = depth[i];
    for (int i = 0; i < topCnt; ++i) if (pw[tops[i]] > mxPw) mxPw = pw[tops[i]];
    high += mxPw; // 此时全员预备队、剩余时间都够

    ll lo = 0, hi = high; // 可行性随时间单调，二分最小可行时间
    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    printf("%lld\n", lo);
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:10
# update_at: 2026-10-02 01:10

import sys
from bisect import bisect_right
from collections.abc import Callable


def bit_build(size: int) -> list[int]:
    """建容量为 size 的全 1 树状数组：t[i] 管 (i-lowbit(i), i] 这段连续下标。"""
    return [0] + [i & -i for i in range(1, size + 1)]


def bit_add(t: list[int], i: int, delta: int) -> None:
    """单点增减：把下标 i 的可用计数加 delta（下标从 0 起）。"""
    i += 1
    while i < len(t):
        t[i] += delta
        i += i & -i


def bit_sum(t: list[int], i: int) -> int:
    """前缀和：下标 [0, i] 里还剩几支没用的军队（i 为 -1 时得 0）。"""
    s = 0
    i += 1
    while i > 0:
        s += t[i]
        i -= i & -i
    return s


def bit_kth(t: list[int], q: int) -> int:
    """找第 q 个 1 的下标：可用军队按序数出第 q 支，树上倍增下降 O(log n)。"""
    idx, bit = 0, 1 << (len(t).bit_length() - 1)
    while bit:
        nxt = idx + bit
        if nxt < len(t) and t[nxt] < q:   # 这一段整段都不够 q 个，跳过去
            q -= t[nxt]
            idx = nxt
        bit >>= 1
    return idx


def min_time(feasible: Callable[[int], bool], high: int) -> int:
    """可行性随时间单调：在 [0, high] 上二分出最小可行时间。"""
    lo, hi = 0, high
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = next(data) - 1, next(data) - 1, next(data)
        adj[u].append((v, w))
        adj[v].append((u, w))
    m = next(data)
    armies = [next(data) - 1 for _ in range(m)]   # 各军队驻扎的城市

    # 从根出发的迭代 DFS：一次拿到父指针、到根距离、子表和先根序
    parent = [-1] * n
    parent[0] = 0             # 根的父亲记成自己，回头时不会被当成孩子
    depth = [0] * n           # 各城市到首都的距离
    pw = [0] * n              # 到父边的权值（根儿子用得上）
    children: list[list[int]] = [[] for _ in range(n)]
    order: list[int] = []
    stack = [0]
    while stack:
        x = stack.pop()
        order.append(x)
        for y, w in adj[x]:
            if y == parent[x]:
                continue
            parent[y] = x
            depth[y] = depth[x] + w
            pw[y] = w
            children[x].append(y)
            stack.append(y)

    # 倍增表：判定时让到不了根的军队 O(log n) 跳到 limit 内最高的祖先
    log = (n - 1).bit_length()                  # 2^log ≥ 最长链
    up = [[0] * n for _ in range(log)]
    up[0] = parent[:]                            # 根指向自己，跳不出去
    for k in range(1, log):
        prev, row = up[k - 1], up[k]
        for x in range(n):
            row[x] = prev[prev[x]]

    # 每支军队属于哪个根儿子的子树（根的儿子上不算，-1 表示没有"自己的子树"）
    origin = [-1] * n
    for x in order[1:]:
        origin[x] = x if parent[x] == 0 else origin[parent[x]]

    tops = sorted(children[0], key=lambda c: -pw[c])   # 需求按边权从大到小
    tid = {c: i for i, c in enumerate(tops)}
    armies.sort(key=lambda s: depth[s])          # 按到根距离升序
    d_sorted = [depth[s] for s in armies]
    groups: list[list[int]] = [[] for _ in tops]     # 每个根儿子有哪些军队
    for idx, s in enumerate(armies):
        c = origin[s]
        if c != -1:
            groups[tid[c]].append(idx)
    gd = [[depth[armies[i]] for i in g] for g in groups]   # 组内同样升序

    cp = [0] * n          # 本轮检查点标记
    cov = [0] * n         # 根到此点是否已有检查点
    unc = [0] * n         # 子树里是否还有没被覆盖的叶子

    def feasible(limit: int) -> bool:
        """limit 小时内能否让每条「首都→边境」路径上都有检查点。"""
        f = bisect_right(d_sorted, limit)        # 能走到首都的军队数
        marks: list[int] = []
        for idx in range(f, m):                  # 走不到首都的：原地走到最高可达祖先
            s = armies[idx]
            th = depth[s] - limit                # 祖先距离下限，恒大于 0，跳不进根
            x = s
            for k in range(log - 1, -1, -1):
                y = up[k][x]
                if depth[y] >= th:
                    x = y
            cp[x] = 1
            marks.append(x)

        cov[0] = cp[0]
        for x in order[1:]:                      # 检查点沿先根序向下渗透
            cov[x] = cp[x] or cov[parent[x]]
        for x in reversed(order):                # 自底向上找「还有裸叶子」的子树
            if cov[x]:
                unc[x] = 0
            elif children[x]:
                unc[x] = 0
                for ch in children[x]:
                    if unc[ch]:
                        unc[x] = 1
                        break
            else:
                unc[x] = 1                       # 叶子且从根到此无检查点
        needs: list[int] = []
        for c in tops:
            if unc[c]:
                needs.append(c)
                if len(needs) > f:               # 需求比预备队还多，直接判负
                    break

        ok = len(needs) <= f
        if ok:
            t = bit_build(f)                     # 只给能到根的军队编号 [0, f)
            used = bytearray(m)
            curs = [-2] * len(tops)              # -2 = 该组还没算过可动上界
            for c in needs:
                g, gtid = groups[tid[c]], tid[c]
                if g:                            # 优先用"自己子树"的军队免费落在 c
                    cur = curs[gtid]
                    if cur == -2:
                        cur = bisect_right(gd[gtid], limit) - 1
                    while cur >= 0 and used[g[cur]]:
                        cur -= 1
                    curs[gtid] = cur
                    if cur >= 0:
                        idx = g[cur]
                        used[idx] = 1
                        bit_add(t, idx, -1)
                        continue
                # 否则从首都折返下到 c：耗时 depth+w ≤ limit，即挑剩余时间够的最弱一支
                pos = bisect_right(d_sorted, limit - pw[c]) - 1
                q = bit_sum(t, pos)
                if q == 0:
                    ok = False
                    break
                idx = bit_kth(t, q)
                used[idx] = 1
                bit_add(t, idx, -1)

        for x in marks:                          # 清掉本轮检查点，供下次判定复用
            cp[x] = 0
        return ok

    # 每支军队最多盖住一个根儿子子树，m 支盖不齐 k 个子树时无解
    if len(tops) > m:
        print(-1)
        return
    high = max(depth) + max(pw[c] for c in tops)   # 此时全员预备队、剩余时间都够
    print(min_time(feasible, high))


if __name__ == "__main__":
    solve()

复杂度

预处理：DFS 建根 $O(n)$ ，倍增表 $O(n \log n)$ ，军队按到根距离排序 $O(m \log m)$ 。
单次判定：走不到首都的军队各倍增一次 $O(m \log n)$ ，两遍覆盖统计 $O(n)$ ，匹配中每个需求做 $O(\log m)$ 的树状数组操作 $O(k \log m)$ （ $k$ 为根儿子数），合计 $O(n + m \log n)$ 。
二分：上界 $\max \mathrm{depth} + \max w_c \leqslant 5 \times 10^{13}$ ，约 $47$ 轮。总时间 $O\bigl((n \log n + (n + m \log n) \cdot \log C)\bigr)$ ，空间 $O(n \log n + m)$ 。

本题限时 1000 ms：常数不小（每轮判定都要过一遍 $O(n)$ 统计和最多 47 轮二分），Python 存在 TLE 风险，本地验证以放宽时限后的输出正确为准；同一算法在 C++ 里就是倍增 + 树状数组的标准写法，时间非常宽裕。

总结

「最小化最大耗时」→ 二分答案，全部难点收进判定。
覆盖具有子树包含关系：走到任何落点都不如停在半路的祖先，或穿过首都落到根儿子——有效落点只有「路径祖先」和「根儿子」两类。
走不到首都的军队只能落在路径上，取最高可达点是唯一最优，落点因此确定；剩下的军队是预备队。
判定归结为：裸叶子所在的根儿子子树（需求）与预备队按 $w_c$ 对剩余时间做 1-1 匹配，降序 + 免费优先 + 最小可用剩余即贪心正确。
倍增求最高可达祖先，树状数组维护「可用且剩余够」的最弱预备队；根儿子数超过军队数即 $-1$ 。

图示解析

下图是完整判定流水线，二分外层与判定内层各司其职：

flowchart TD
    S["预处理：建根、倍增表、军队按 depth 排序"] --> B{"二分时间 T"}
    B --> C1["分类：depth > T 走不到首都<br/>倍增落到最高可达祖先并建点"]
    C1 --> C2["覆盖统计：根向下渗透、自底向上找裸叶子"]
    C2 --> C3{"每个裸根儿子子树配一支预备队<br/>降序：先免费本组，再最小剩余折返"}
    C3 -->|"全部配上"| Y["可行 → 收紧上界"]
    C3 -->|"有需求没人"| N["不可行 → 放宽下界"]
    Y --> B
    N --> B
    B -->|"lo == hi"| O["输出答案；根儿子数 > m 输出 -1"]

读者应关注：判定里三步是顺序依赖的——先让「走不到首都」的军队把确定的覆盖落下来，才能统计出真正的需求；预备队匹配只处理统计后的残余需求，三步合起来才等价于原问题。

目录