逐个击破

形式化题目

给定一棵 $N$ 个节点、 $N-1$ 条边的带权无向树 $T=(V,E)$ ，边 $e\in E$ 的权为 $w_e\geqslant 0$ 。给定关键点集 $S\subseteq V$ ， $|S|=K$ 。

选择一个边集 $D\subseteq E$ 删去（破坏），要求：在 $T-D$ 中， $S$ 中任意两个节点之间都没有路径。求

\min_{D \text{ 合法}} \sum_{e\in D} w_e .

记 $R = E\setminus D$ ，则 $T-D = (V,R)$ 是一片森林，" $S$ 两两不连通"等价于

\text{每个 } R \text{-连通块内至多包含一个 } S \text{ 中的节点}.

又因为

\sum_{e\in D} w_e = \sum_{e\in E} w_e - \sum_{e\in R} w_e ,

所以最小化删除代价等价于在满足上述块内敌城数 $\leqslant 1$ 的森林中，最大化保留边权和。

暴力解法

思路

最直接的想法：枚举每条边"删 / 留"。树只有 $N-1$ 条边，所以合法的删边集就是 $2^{N-1}$ 个 01 序列中的一个。

choose[e] = 1 表示破坏第 $e$ 条公路；
递归到叶子后，把所有 choose[e] = 0（保留）的边并进并查集；
把每个敌城所在连通块的根记下来，如果出现重复的根，说明两队敌军仍然连通，方案非法；
合法时累加被破坏边的代价，更新最小值。

这个暴力是"教科书式"的：先生成完整方案，再统一检查、统一统计。它覆盖了全部删边方案，因此答案一定正确。

代码

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/**
 * 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-21 21:40
 * update_at: 2026-10-21 21:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法：直接枚举「每条公路破坏还是保留」（共 2^(n-1) 种方案），
// 对每个完整方案把保留的边连起来，检查 K 个敌城是否两两不连通，合法就更新最小代价。
// 复杂度 2^(n-1) * n，n = 10 时约 500 次叶子检查，只适合很小的数据；
// 它完全没有用到「按边权降序 + 并查集」的正解思路，因此可以和 main.cpp 独立对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 15;  // 城市数上限，只服务小数据（n <= 10）

int n;               // 城市数
int k;               // 被敌军占领的城市数
bool is_enemy[MAXN]; // is_enemy[x]：城市 x 是否被敌军占领

int edge_u[MAXN];    // edge_u[e]：第 e 条公路的一端
int edge_v[MAXN];    // edge_v[e]：第 e 条公路的另一端
ll edge_w[MAXN];     // edge_w[e]：破坏第 e 条公路的代价

int choose[MAXN];    // 01 序列：choose[e] = 1 表示破坏第 e 条公路，0 表示保留

ll best_cost;        // 当前搜到的最小破坏代价

int dsu_parent[MAXN];  // 并查集父节点，只在 check() 里临时用

int dsu_find(int x) {
    while (dsu_parent[x] != x) {
        dsu_parent[x] = dsu_parent[dsu_parent[x]];
        x = dsu_parent[x];
    }
    return x;
}

// 检查当前方案是否合法：把保留的公路连起来，K 个敌城必须落在 K 个不同的连通块里。
bool check() {
    for (int i = 0; i < n; i++) dsu_parent[i] = i;
    for (int e = 1; e <= n - 1; e++) {
        if (choose[e]) continue;  // 这条公路被破坏了，不参与连通
        int root_a = dsu_find(edge_u[e]);
        int root_b = dsu_find(edge_v[e]);
        if (root_a != root_b) dsu_parent[root_b] = root_a;
    }

    // 把每个敌城所在连通块的根记下来，出现重复根就说明两队敌军还连着
    bool used_root[MAXN] = {false};
    for (int i = 0; i < n; i++) {
        if (!is_enemy[i]) continue;
        int root = dsu_find(i);
        if (used_root[root]) return false;
        used_root[root] = true;
    }
    return true;
}

// 一层在做一件事：决定第 dep 条公路破坏还是保留。
void dfs_choose(int dep) {
    if (dep > n - 1) {
        // 完整方案已生成，先检查合法性，再算代价并更新答案
        if (!check()) return;
        ll cost = 0;
        for (int e = 1; e <= n - 1; e++) {
            if (choose[e]) cost += edge_w[e];
        }
        if (cost < best_cost) best_cost = cost;
        return;
    }
    for (int i = 0; i <= 1; i++) {
        choose[dep] = i;
        dfs_choose(dep + 1);
    }
    choose[dep] = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int city;
        cin >> city;
        is_enemy[city] = true;
    }
    for (int e = 1; e <= n - 1; e++) {
        cin >> edge_u[e] >> edge_v[e] >> edge_w[e];
    }

    best_cost = 1LL << 60;  // 全破坏一定合法，所以答案有上界
    dfs_choose(1);
    cout << best_cost << '\n';
    return 0;
}

复杂度

叶子有 $2^{N-1}$ 个，每个叶子做一次 $O(N)$ 的并查集检查与代价累加，总时间复杂度 $O(2^{N-1}\cdot N)$ ；空间复杂度 $O(N)$ （边表、choose[] 与递归栈）。

瓶颈

瓶颈不只是" $2^{N-1}$ 太大"这一条。更根本的是：暴力没有给出任何"这条边该不该删"的判据，它只能靠穷举来回避这个判断。所以即使砍掉枚举也无从下手——必须先找到一个可以逐边决策的视角。

数据范围 $N\leqslant 10^5$ 时， $2^{N-1}$ 连想都不用想。暴力只适合 $N\leqslant 10$ 的理解和对拍。

正解

思路

正难则反：从"删"翻成"留"

直接想"删掉哪些边"，要同时照顾 $K$ 个敌城的所有点对，删一条边会牵动一大片点对，判断不出这条边值不值得删。

把问题翻转：不数删了什么，改数留了什么。由形式化部分的恒等式，“最小删边代价"完全等价于"最大保留边权和”，而约束也从" $K$ 个点两两不连通"变形成了一句更好用的话：

保留的边构成森林，每个连通块里至多一个敌城。

“尽量少删"变成了"尽量多收”，而收边天生适合按权值从大到小贪心——这是全题的关键一步。

重边优先：什么时候"必须删"

现在从权值最大的边开始处理。设已处理的边（都被保留或破坏）拼出一些块，当前处理 $e=(u,v)$ ， $u$ 、 $v$ 分别落在块 $C_u$ 、 $C_v$ ：

$C_u$ 、 $C_v$ 里都有敌城：取敌城 $a\in C_u$ 、 $b\in C_v$ 。在树中 $a$ 到 $b$ 的唯一路径就是" $a \rightsquigarrow u$ ，再过 $e$ ，再 $v \rightsquigarrow b$ "。如果保留 $e$ ， $a$ 与 $b$ 立刻连通，而之后的合并只会让块更大、不会拆开，所以任何合法方案都救不回来。这条边是强制项：必须破坏，代价 $w_e$ 逃不掉。
至少一边没有敌城（不妨设 $C_v$ 没有）：可以放心保留。它只把无城那一侧并进来，块内敌城数不增加。

第二点的"可以放心保留"需要一句论证，否则只是直觉：假设某个最优解 $R^{*}$ 破坏了 $e$ ，把 $e$ 加回去。加 $e$ 会让 $C_u$ 与 $C_v$ 合并，敌城总数是两个块敌城数之和，其中 $C_v$ 贡献 $0$ ，仍然 $\leqslant 1$ ，合法；代价还少付 $w_e\geqslant 0$ 。所以存在一个保留 $e$ 的最优解——这就是交换论证：不是"每个最优解都保留它"，而是"总能把最优解改造成保留它的样子"，足够让贪心继续。

换个更整齐的口径看同一件事：把 $K$ 个敌城缩成同一个超级点 $s$ ，原树就变成一张含 $s$ 的多重图 $G'$ 。此时

R \text{ 满足「每块至多一个敌城」} \iff R \text{ 在 } G' \text{ 中无环}.

因为 $G'$ 里的环只有一种来源：原树中一条两端都是敌城的路径，两端都缩到 $s$ 后首尾相接成环。于是本题变成"在 $G'$ 里求最大权生成森林"，而按权降序贪心选边正是 Kruskal；“两端块是否都含敌城"就是"加这条边会不会成环”。这就解释了为什么正解的骨架和最小生成树一模一样。

"反悔不会更优"的口径也能说得更直白：被破坏的边，是在两端块各自已经含敌城的时刻被破坏的，而这两块由更重的边连成、之后只会继续变大；把这条边加回来必然连通两队敌军，任何后续选择都无法撤销。所以贪心删掉的边没有反悔余地，保留的边又被上面的交换论证保护，两者合起来就是正确性。

并查集怎么带"有没有敌城"

普通 Kruskal 的并查集只需要"是否同块"。这里每块额外带一个布尔标记 has_enemy[根]：这块里有没有敌城。合并时把两个标记取或。

样例推演

样例： $N=5$ ，敌城 $\{1,2,4\}$ ，边为 $(1,0,4)$ 、 $(1,3,8)$ 、 $(2,1,1)$ 、 $(2,4,3)$ 。按权值降序处理，初始每个点自成一集合：

顺序	边	权	两端块是否都有敌城	决策	答案累计
1	1 到 3	8	一块有敌城，另一块没有	保留，合并	0
2	1 到 0	4	一块有敌城，另一块没有	保留，合并	0
3	2 到 4	3	两块都有敌城	破坏	3
4	2 到 1	1	两块都有敌城	破坏	4

表里"边"一列是无向边的两个端点，"两端块是否都有敌城"指这两个端点当前所属的并查集块里各自有没有敌城（初始时每个点自成一集合），"答案累计"是到目前为止被迫付掉的破坏代价。逐行看块的变化：第 1 行后点 1、3 合为一块（因为敌城 1 在里面，此块带敌城标记）；第 2 行后点 1、3、0 合为一块；第 3 行时点 2 与点 4 都还是含敌城的独立块，保留它就会把两队敌军连起来，只能破坏；第 4 行同理，点 2 所在的块与点 1 所在的块都含敌城，也必须破坏。

所以总代价是 $3+1=4$ ，与样例答案一致。注意最先处理的最贵边 $(1,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/**
 * 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-21 21:40
 * update_at: 2026-10-21 21:40
 */
// P2700 逐个击破
// 正难则反：直接想「删掉哪些边代价最小」要同时照顾所有敌城，很难；翻转成
// 「尽量多保留边，使代价和最大」，答案 = 总边权 - 最大保留边权。
// 保留的边构成森林，要求：每个连通块里至多有一个敌城。
//
// 贪心做法（本质是 Kruskal）：按边权从大到小扫，能用（不会把两个含敌城的块粘在一起）
// 就保留（不花钱），不能用就必须破坏（付这条边的代价）。
// 正确性直觉：重边先决定，任何偏离都只能拿更轻的边来换，不会更优。
//
// 复杂度：排序 O(n log n) + 并查集近似 O(n α(n))，空间 O(n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 100000 + 5;  // 城市数上限 N <= 1e5

struct Edge {
    int u;   // 公路一端
    int v;   // 公路另一端
    ll w;    // 破坏这条公路的代价
};
Edge edge[MAXN];  // edge[1..n-1]：树上的 n-1 条公路

int dsu_parent[MAXN];  // dsu_parent[x]：x 的父亲，x 是根时等于 x
int dsu_size[MAXN];    // dsu_size[x]：x 是根时这个连通块的城市数
bool has_enemy[MAXN];  // has_enemy[根]：这个连通块里有没有被敌军占领的城市

// 边权大的排在前面：先决定最贵的边留不留，符合「重边优先」。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w > b.w;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合，返回合并后的根；两端本来就连通时返回 -1。
// dsu_size[x] 是 x 当根时集合的城市数，用来按大小合并。
int dsu_merge(int a, int b) {
    int root_a = dsu_find(a);
    int root_b = dsu_find(b);
    if (root_a == root_b) return -1;
    // 小集合并到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return root_a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    // 城市编号从 0 开始，并查集也按 0..n-1 开
    for (int i = 0; i < n; i++) {
        dsu_parent[i] = i;
        dsu_size[i] = 1;
        has_enemy[i] = false;
    }

    // 标记被敌军占领的城市
    for (int i = 1; i <= k; i++) {
        int city;
        cin >> city;
        has_enemy[city] = true;
    }

    for (int i = 1; i <= n - 1; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    sort(edge + 1, edge + n, cmp_edge);  // edge[1 .. n-1] 按代价降序

    ll answer = 0;  // 累加必须破坏的公路代价
    for (int i = 1; i <= n - 1; i++) {
        int root_u = dsu_find(edge[i].u);
        int root_v = dsu_find(edge[i].v);
        // 树上不会出现这种情形（保留边构成的子图永远无环），这里只是防御性判断
        if (root_u == root_v) continue;

        if (has_enemy[root_u] && has_enemy[root_v]) {
            // 两端连通块里都有敌城：保留这条边等于把两队敌军连起来，只能破坏
            answer += edge[i].w;
            continue;
        }

        // 至少有一端没有敌城：保留这条边是安全的，把两块合成一块
        int root = dsu_merge(root_u, root_v);
        has_enemy[root] = has_enemy[root_u] || has_enemy[root_v];
    }

    cout << answer << '\n';
    return 0;
}

Python 版本与 main.cpp 完全同算法，find 用迭代路径压缩避免递归深度问题：

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#!/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-21 21:40
# update_at: 2026-10-21 21:40
#
# P2700 逐个击破
# 正难则反：不直接想「删哪些边」，而是想「尽量多保留边」，答案 = 总边权 - 最大保留边权。
# 保留的边构成森林，要求每个连通块里至多有一个敌城。
# 按边权从大到小扫：这条边若把两个「都含敌城」的块连起来，就必须破坏（付代价）；
# 否则保留它、合并两块。这和最小生成树的 Kruskal 是同一套并查集框架。

import sys

type Edge = tuple[int, int, int]  # (一端 u, 另一端 v, 破坏代价 w)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)

    has_enemy = [False] * n  # has_enemy[根]：这个连通块里有没有被敌军占领的城市
    for _ in range(k):
        has_enemy[next(data)] = True  # 城市编号从 0 开始

    edges: list[Edge] = [(next(data), next(data), next(data)) for _ in range(n - 1)]

    parent = list(range(n))  # parent[x]：x 的父节点，x 是根时等于 x
    size = [1] * n           # size[x]：x 是根时这个连通块的城市数

    answer = 0
    for u, v, w in sorted(edges, key=lambda edge: edge[2], reverse=True):  # 代价大的先决定
        root_u, root_v = find(parent, u), find(parent, v)
        if has_enemy[root_u] and has_enemy[root_v]:
            answer += w  # 保留它会把两队敌军连起来，只能破坏
            continue
        if size[root_u] < size[root_v]:  # 小集合并到大集合下面
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        has_enemy[root_u] = has_enemy[root_u] or has_enemy[root_v]

    print(answer)


if __name__ == "__main__":
    solve()

复杂度

排序是瓶颈： $O(N\log N)$ 。之后每条边做两次 dsu_find，并查集带路径压缩与按大小合并，均摊 $O(\alpha(N))$ ，扫描部分 $O(N\alpha(N))$ 。

时间复杂度： $O(N\log N)$ 。
空间复杂度： $O(N)$ （边表 + 并查集三个数组）。

对比暴力的 $O(2^{N-1}\cdot N)$ ， $N=10^5$ 时差距不可计量。

验证

官方样例：main.cpp 与 main.py 都 AC。
随机对拍：gen.py 生成 320 组小数据（ $N\leqslant 10$ ，边权含 $0$ 与 $10^6$ 量级，链形与随机形， $K$ 取 $2$ 、 $N$ 与随机值），标准答案取 brute.cpp 的输出：
- roj-local-judge-lite main.cpp --data-dir <目录> --output-format json → AC 320/320
- roj-local-judge-lite main.py --data-dir <目录> --output-format json → AC 320/320
极限规模自测： $N=10^5$ 的深链 + $50000$ 个敌城，main.cpp AC 40 ms / 3072 KB，main.py AC 221 ms / 49084 KB。

总结

本题的全部难度集中在视角转换上：

正难则反。“删哪些边"是全局减法，判不出单条边的去留；改成"留哪些边”，约束变成"每块至多一个敌城"，目标变成最大化保留边权和。
重边优先。按权值降序处理时，最贵的边一旦连接了两个都含敌城的块，就必须删——因为它是两侧敌城之间唯一通路，且之后只会合并、不能拆分。反之若一侧无城，必定存在最优解保留它（交换论证）。
实现即 Kruskal。把 $K$ 个敌城缩成一个超级点后，“块内至多一个敌城"正好等于"无环”，于是问题就是最大权生成森林。并查集多带一个 has_enemy 标记即可，其余骨架与 MST 的 Kruskal 完全相同。

一句话记住它：从大到小加边，只在"加了就会让两队敌军连通"的时候，才付这条边的代价。

目录