[NOIP2012-提高] 疫情控制

形式化题目

给定一棵 $n$ 个点的无根树，1 号点为根（首都）。要求选出若干个非根点建立检查点，使根到每个叶子的路径上都至少经过一个检查点。现有 $m$ 支军队，初始驻扎在给定节点（允许同点驻扎多支，保证不在根）。每支军队可以沿树边移动，并且恰好在一个非根节点建立一处检查点；走过一条长度为 $w$ 的边耗时 $w$ ，不同军队同时行动，总时间等于最慢那支军队的耗时。求控制疫情的最少时间；若无法做到，输出 $-1$ 。

样例中 $n=4$ ，边为 $1-2$ （长 $1$ ）、 $1-3$ （长 $2$ ）、 $3-4$ （长 $3$ ），两支军队都在 2 号点：

graph TD
    R["1 首都"] ---|"1"| A["2<br/>边境"]
    R ---|"2"| B["3"]
    B ---|"3"| C["4<br/>边境"]

观察这棵树：叶子是 2 和 4，根到它们的路径分别是 $1\to2$ 、 $1\to3\to4$ 。一支军队原地在 2 号点设卡，第二支从 2 号点经首都走到 3 号点设卡，同时封锁两条路径，耗时 $1+2=3$ 小时，故输出 3。

正解

思路

朴素做法：枚举每支军队的最终驻扎点与检查点位置组合，再逐一验证叶子路径，是指数级的，无法承受 $n \leqslant 50000$ 。需要把"军队怎么走"和"全局是否覆盖"两件事分开优化。

观察一：能上跳就上跳（支配关系）。 检查点越靠近根，覆盖的叶子越多。一支从 $v$ 出发的军队若停在祖先 $u$ ，就能覆盖整棵 $u$ 的子树；从 $u$ 继续上移到父亲只会让覆盖范围变大，耗时也不增加。因此对任何军队，在时限内停到最高可达的祖先永远不劣于停在更低处——但首都本身不能设卡，所以"最高"要区分两类情况：

走不到首都（ $x < \mathrm{dist}[v]$ ）：唯一最优解是停在可达的最高祖先 $u \neq 1$ ，用倍增在 $O(\log n)$ 内求出；
走得到首都（ $x \geqslant \mathrm{dist}[v]$ ）：走到首都本身不产生覆盖，但获得了机动性——既可以在上跳途中顺路停在原孩子 $\mathrm{son}$ （代价 $\mathrm{dist}[v]-w(1,\mathrm{son}) \leqslant \mathrm{dist}[v] \leqslant x$ ，恒可行），也可以继续走到首都、再下到其他孩子 $c$ （要求剩余时间 $\mathrm{rest}=x-\mathrm{dist}[v] \geqslant w(1,c)$ ）。

观察二：答案单调，二分时间。 若 $x$ 小时可行，则 $x+1$ 也一定可行（军队只会走得更远），于是二分答案，只需求出判定函数 $\mathrm{check}(x)$ 。

观察三：需求总在根的孩子这一层。 根的孩子 $c$ 被"覆盖"当且仅当 $c$ 的子树里每条到叶子的路径都有检查点。自底向上统计即可： $\mathrm{cov}[u] = $（$ u$ 处有军队）或（ $u$ 的所有孩子都被覆盖；叶子则只看自己）。没有被覆盖的根的孩子就是当前的需求，一支军队把检查点建在 $c$ 上就能一次性解决 $c$ 的全部需求。

于是 $\mathrm{check}(x)$ 按以下顺序执行：

上跳分流：走不到首都的军队停在最高可达点并打标记；走得到首都的按剩余时间 $\mathrm{rest}$ 升序收集（按到根时长降序排序即得）。
覆盖统计：自底向上求出每个根的孩子是否已被标记的军队覆盖。
"回不去"特判：对走到首都的军队，若原孩子 $c$ 还没被覆盖、且 $\mathrm{rest} < w(1,c)$ （从首都下不回去了），就直接让它原路停在 $c$ 处，把 $c$ 的需求消掉——这是"决策包容性"：这种军队留在原地只会比把它投到别处更优，因为它离开原孩子后就再也无法解决 $c$ 了。反之若 $\mathrm{rest} \geqslant w(1,c)$ ，它既能解决 $c$ 也能解决别人，先进匹配池不亏。
双指针匹配：剩下的需求按边权升序，匹配池（剩余时间升序）里每次取"第一个够用"的军队，能全部配上则 $x$ 可行。

无解判定：一个根的孩子必须有至少一支军队进入其子树，且一支军队只能覆盖一个孩子，因此 $m <$ 根的孩子数时直接输出 $-1$ ；否则把二分上界取为全树边权和 $\Sigma w$ ，此时所有军队都能走到首都且剩余时间充足，必可行。

以样例演示 $\mathrm{check}$ 的分流与匹配（两支军队初始都在 2 号点， $\mathrm{dist}=1$ ，根之子为 2（边权 1）和 3（边权 2））：

二分值 $x$	分流	覆盖统计与特判	双指针匹配	结论
$x=2$	两军都能到首都，剩余各 $1$	无标记，根之子 2、3 均为需求； $\mathrm{rest}=1 \nless w(1,2)=1$ ，特判不触发，全部进池 $[1,1]$	需求 2（ $w=1$ ）配到 $1$ ；需求 3（ $w=2$ ）池中只剩 $1$ ，不够	不可行
$x=3$	两军都能到首都，剩余各 $2$	同上，进池 $[2,2]$	需求 2 配 $2$ ，需求 3 配 $2$	可行

二分最终落在最小可行值 3，与题解样例一致。注意若把"走到首都的军队只能从首都往下走"作为模型，样例之外会出现把顺路停在原孩子的情况误判为不可行的漏洞，特判第 3 步正是为此补上。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19/**
 * 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 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> DIST, WTOP; vector<vector<int> > UP, CH; vector<int> ORDER, TOP, RC, ARMY; vector<ll> NEG_D; int LOGN, M;
int lift_node(int v, ll x){ ll threshold=DIST[v]-x; int u=v; for(int j=LOGN-1;j>=0;j--){int a=UP[j][u]; if(a && DIST[a]>=threshold) u=a;} return u; }
vector<char> subtree_covered(vector<char> &vis){ vector<char> cov(DIST.size()); for(int idx=(int)ORDER.size()-1; idx>=0; idx--){int u=ORDER[idx]; if(vis[u]){cov[u]=1; continue;} if(!CH[u].empty()){char ok=1; for(int i=0;i<(int)CH[u].size();i++) if(!cov[CH[u][i]]){ok=0;break;} cov[u]=ok;}} return cov; }
bool feasible_time(ll x){ vector<char> vis(DIST.size()); int split=lower_bound(NEG_D.begin(),NEG_D.end(),-x)-NEG_D.begin(); for(int i=0;i<split;i++) vis[lift_node(ARMY[i],x)]=1; vector<char> cov=subtree_covered(vis); vector<ll> pool; for(int i=split;i<M;i++){int v=ARMY[i]; ll rest=x-DIST[v]; int son=TOP[v]; if(!cov[son] && rest<WTOP[son]) cov[son]=1; else pool.push_back(rest);} int j=0; for(int idx=0;idx<(int)RC.size();idx++){int c=RC[idx]; if(cov[c]) continue; ll w=WTOP[c]; while(j<(int)pool.size() && pool[j]<w) j++; if(j==(int)pool.size()) return false; j++;} return true; }
struct Edge{int v; ll w;};
bool cmp_army(int a,int b){ return DIST[a] > DIST[b]; }
bool cmp_root_child(int a,int b){ return WTOP[a] < WTOP[b]; }
int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; if(!(cin>>n)) return 0; vector<vector<Edge> > adj(n+1); ll total=0; for(int i=0;i<n-1;i++){int u,v;ll w;cin>>u>>v>>w; adj[u].push_back({v,w}); adj[v].push_back({u,w}); total+=w;} DIST.assign(n+1,0); CH.assign(n+1,vector<int>()); TOP.assign(n+1,0); WTOP.assign(n+1,0); vector<int> fa(n+1); vector<char> seen(n+1); queue<int> q; seen[1]=1; q.push(1); while(!q.empty()){int u=q.front(); q.pop(); for(int i=0;i<(int)adj[u].size();i++){int v=adj[u][i].v; ll w=adj[u][i].w; if(seen[v]) continue; seen[v]=1; DIST[v]=DIST[u]+w; CH[u].push_back(v); fa[v]=u; TOP[v]=(u==1?v:TOP[u]); if(u==1) WTOP[v]=w; ORDER.push_back(v); q.push(v);}} LOGN=1; while((1<<LOGN)<=n) LOGN++; UP.assign(LOGN, vector<int>(n+1)); for(int v=0;v<=n;v++) UP[0][v]=fa[v]; for(int j=1;j<LOGN;j++) for(int v=0;v<=n;v++) UP[j][v]=UP[j-1][UP[j-1][v]]; cin>>M; ARMY.resize(M); for(int i=0;i<M;i++) cin>>ARMY[i]; sort(ARMY.begin(),ARMY.end(),cmp_army); NEG_D.resize(M); for(int i=0;i<M;i++) NEG_D[i]=-DIST[ARMY[i]]; RC=CH[1]; sort(RC.begin(),RC.end(),cmp_root_child); if(M<(int)CH[1].size()){cout<<-1<<'\n';return 0;} ll lo=0,hi=total; while(lo<hi){ll mid=(lo+hi)/2; if(feasible_time(mid)) hi=mid; else lo=mid+1;} cout<<lo<<'\n'; 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#!/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 10:34
# update_at: 2026-10-02 10:34

import sys
from bisect import bisect_left
from collections import deque

DIST: list[int] = []      # 每个点到根的总时长
UP: list[list[int]] = []  # UP[j][v]：v 的 2^j 级祖先，0 表示不存在
CH: list[list[int]] = []  # 以 1 为根的孩子表
ORDER: list[int] = []     # BFS 层序（不含根），倒序即自底向上
TOP: list[int] = []       # 每个点正上方的根之子，军队"原驻地"看它
WTOP: list[int] = []      # 根之子到根的边权（仅深度 1 有点义）
RC: list[int] = []        # 根的孩子，按边权升序
ARMY: list[int] = []      # 军队所在点，按到根时长降序
NEG_D: list[int] = []     # 对应的 -DIST，升序，供 bisect 判断能否走到首都
LOG = 0
M = 0


def lift(v: int, x: int) -> int:
    """倍增上跳：返回 x 小时内能到达的最高祖先（到不了首都）。"""
    threshold = DIST[v] - x  # 目标 dist 至少要这么大；为正数 ⇒ 不会跳到首都
    u = v
    for j in range(LOG - 1, -1, -1):
        a = UP[j][u]
        if a and DIST[a] >= threshold:
            u = a
    return u


def subtree_covered(vis: bytearray) -> bytearray:
    """自底向上标记：每个点的子树是否已被驻扎军队完整覆盖。"""
    cov = bytearray(len(DIST))
    for u in reversed(ORDER):
        if vis[u]:
            cov[u] = 1
            continue
        children = CH[u]
        if children:  # 叶子没有孩子：没军队驻扎就是没覆盖
            covered = 1
            for c in children:
                if not cov[c]:
                    covered = 0
                    break
            cov[u] = covered
    return cov


def feasible(x: int) -> bool:
    """判断 x 小时内能否控制疫情：上跳分流 → 覆盖统计 → 贪心匹配。"""
    vis = bytearray(len(DIST))
    split = bisect_left(NEG_D, -x)  # 前缀到不了首都，后缀可以
    for i in range(split):
        vis[lift(ARMY[i], x)] = 1
    cov = subtree_covered(vis)

    # 能走到首都的军队按剩余时间升序（到根时长降序），剩余时间不够回到原孩子的
    # 先留在原地把原孩子盖掉，剩下的进匹配池——这一步是"决策包容性"的特判
    pool: list[int] = []
    for i in range(split, M):
        v = ARMY[i]
        rest = x - DIST[v]
        son = TOP[v]
        if not cov[son] and rest < WTOP[son]:
            cov[son] = 1  # 原孩子还没盖住，且回不去：直接留在原地
        else:
            pool.append(rest)

    # 未覆盖的根之子按边权升序，剩余时间取"刚刚够用"的军队（双指针）
    j = 0
    pool_len = len(pool)
    for c in RC:
        if cov[c]:
            continue
        w = WTOP[c]
        while j < pool_len and pool[j] < w:
            j += 1
        if j == pool_len:
            return False
        j += 1
    return True


def solve() -> None:
    global LOG, M, RC, ARMY, NEG_D
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    adj: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]
    total = 0  # 全部边权之和，充当二分上界
    for _ in range(n - 1):
        u, v, w = next(data), next(data), next(data)
        adj[u].append((v, w))
        adj[v].append((u, w))
        total += w

    # 从首都 BFS 定根：父亲、层序、到根时长、根之子
    DIST.extend([0] * (n + 1))
    CH.extend([] for _ in range(n + 1))
    TOP.extend([0] * (n + 1))
    WTOP.extend([0] * (n + 1))
    fa = [0] * (n + 1)
    seen = bytearray(n + 1)
    seen[1] = 1
    queue = deque([1])
    while queue:
        u = queue.popleft()
        for v, w in adj[u]:
            if seen[v]:
                continue
            seen[v] = 1
            DIST[v] = DIST[u] + w
            CH[u].append(v)
            fa[v] = u
            TOP[v] = v if u == 1 else TOP[u]
            if u == 1:
                WTOP[v] = w
            ORDER.append(v)
            queue.append(v)
    del adj, seen

    LOG = (n).bit_length()
    UP.extend([[0] * (n + 1) for _ in range(LOG)])
    for v in ORDER:
        UP[0][v] = fa[v]
    for j in range(1, LOG):
        row, prev = UP[j], UP[j - 1]
        for v in ORDER:
            row[v] = prev[prev[v]]

    M = next(data)
    ARMY = sorted((next(data) for _ in range(M)), key=lambda v: DIST[v], reverse=True)
    NEG_D = [-DIST[v] for v in ARMY]
    RC = sorted(CH[1], key=lambda c: WTOP[c])

    if M < len(CH[1]):  # 军队数少于根之子数，一个子树都分不到
        print(-1)
        return

    lo, hi = 0, total  # 边权全取，所有军队都能走到首都，必可行
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    print(lo)


if __name__ == "__main__":
    solve()

复杂度

设二分轮数为 $T = O(\log \Sigma w)$ 。每轮中：军队倍增上跳共 $O(m\log n)$ ，自底向上的覆盖统计与贪心匹配均为 $O(n + m)$ ，排序（军队按到根时长、根的孩子按边权）均在读入后预处理完成，轮内无需再排。总时间复杂度 $O(T\cdot(m\log n + n))$ ，空间 $O(n\log n)$ （倍增表）。与标准 C++ 解法同阶； $n = m = 50000$ 时 Python 可能面临 TLE 风险，但算法本身不引入额外量级。

总结

本题是"二分答案 + 倍增 + 贪心匹配"的组合：二分把最优化问题转为判定问题；"上跳支配"把每支军队的走法收敛为唯一的最高停点或一份剩余时间；"需求只在根的孩子层"把覆盖验证压成一次自底向上统计；最后用"回不去原孩子就留在原地"的特判加双指针匹配完成判定。 $m$ 小于根的孩子数即无解，否则全树边权和是可行上界。

[NOIP2012-提高] 疫情控制

目录

形式化题目

正解

思路

代码

复杂度

总结