[蓝桥杯 2023 省 B] 砍树

GitHub跳转原题关系图返回列表

砍掉一条边会把树分成两半，所以数对 (a,b) 被分开的充要条件就是这条边在 a 到 b 的路径上；问题变成“哪些边被全部 m 条路径跨过”，用 LCA 加树上点差分一次统计。

OJ: luogu

题目 ID: P9246

难度:普及+/提高-

标签:树LCA树上差分倍增图论

创建: 2026-10-02 15:07

更新: 2026-10-07 12:15

前置题目

luogu P5836[USACO19DEC] Milk Visits SB 正解第三步给每条路径打 diff[a]++、diff[b]++、diff[w]-=2 时，用的正是 A 教的「路径=两条根路径相加，再把公共前缀（根到 LCA）被多算的两份减掉」这一步，只是把 A 的前缀和计数换成点差分值；B 另外叠加了「删边后不连通等价于该边被路径覆盖」的转化与自底向上子树汇总这两步新流程。luogu P3379【模板】最近公共祖先（LCA）P9246 正解的第三步对每条路径求 w=LCA(a_i,b_i) 后打 diff，其 LCA 完全按 P3379 教的 up[j][u] 倍增表、先对齐深度再同步跳实现，A 的这一步被直接复用为差分的预处理；B 新增的是树上点差分与自底向上求和这一额外流程，构成普及 -> 普及+/提高- 的台阶。

后置题目

roj 3633[noip2015-提高] 运输计划P9246 教会的“端点+1、LCA−2 再自底向上求和得到每条边被路径覆盖的次数”被 3633 原样用于统计超标计划的公共边 roj 1553「一本通 4.4 例 2」暗的连锁B 的树上差分逐字复用 A 教的「diff[u]++、diff[v]++、diff[w]-=2」端点打标记与自底向上累加求父边跨越次数这一步，只是把统计对象换成附加边路径，再叠加 c_e 的 0/1/>=2 三分类计数。

形式化题目

给定一棵 $n$ 个结点的树（边按输入顺序编号 $1 \sim n-1$ ）和 $m$ 个无序数对 $(a_i, b_i)$ 。这些数对满足

$a_1, \ldots, a_m$ 互不相同， $b_1, \ldots, b_m$ 互不相同；
$a_i \neq b_j$ 对任意 $i, j$ 成立，也就是说两个集合 $A = \{a_i\}$ 、 $B = \{b_i\}$ 不相交。

要求选出一条边砍断，使得每一对 $a_i, b_i$ 都不再连通。若有多条边可行，输出编号最大的一条；一条都没有则输出 $-1$ 。

关键点在于“不连通”在树上的含义。树中删掉一条边后只剩两个连通块，所以：

$a_i$ 和 $b_i$ 被分开 $\iff$ 被砍的那条边属于 $a_i$ 到 $b_i$ 的唯一路径。

于是题目重新表述为：

求所有满足“被全部 $m$ 条树上路径覆盖”的边中，编号最大的那一条。

样例给出的树结构以及两对 $(3,6)$ 、 $(4,5)$ 的路径如下（边旁数字是输入编号）：

graph TD
    n1((1)) ---|1| n2((2))
    n2 ---|2| n3((3))
    n3 ---|3| n4((4))
    n2 ---|4| n5((5))
    n5 ---|5| n6((6))

$(3,6)$ 的路径是 $3 \to 2 \to 5 \to 6$ ， $(4,5)$ 的路径是 $4 \to 3 \to 2 \to 5$ 。两条路径的公共边只有编号 $2$ 和编号 $4$ ，其中编号更大的是 $4$ ，所以答案是 $4$ 。观察这个例子可以立刻得出：答案必须同时出现在每一条路径上，这正是后面的统计目标。

暴力解法

思路

完全照着题面做，不需要任何结构上的洞察：

枚举砍掉哪一条边（ $n-1$ 种可能）；
把剩下的 $n-2$ 条边用并查集连起来，得到砍边后的两个连通块；
检查每一对 $(a_i, b_i)$ 是否都不连通；
全部合法就更新答案，最后输出编号最大的那条。

第 1 层的选择就是“砍哪一条边”，一共 $n-1$ 种选择，全部枚举一遍就不会漏掉答案。代码里把“检查一种砍法”写成一个独立函数 check_after_cut(cut)，枚举和判定分得很干净，容易确认正确性。

代码

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/**
 * 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-03 11:50
 * update_at: 2026-10-03 11:50
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 思路：直接实现题面。枚举砍掉哪一条边，把剩下的 n-2 条边用并查集连起来，
//       再逐对检查 (a_i, b_i) 是否都不连通；可行的边都试一遍，最后输出编号最大的。
//       完全不利用树的结构，只依赖“删一条边把图分成两半”的直观事实，正确性最直接。
// 规模：每条边都要重建一次并查集，复杂度 O(n^2 α(n))，只适合 n <= 3000 的小数据。
#include <iostream>
using namespace std;

const int MAXN = 3005;

int n, m;
int eu[MAXN], ev[MAXN]; // 树的 n-1 条边，从 1 号下标开始
int qa[MAXN], qb[MAXN]; // m 个待分离的数对
int fa[MAXN];           // 并查集

int find_root(int x) {
    while (fa[x] != x) {
        fa[x] = fa[fa[x]]; // 路径减半，防止链状数据退化
        x = fa[x];
    }
    return x;
}

// 砍掉编号为 cut 的边后，检查是不是每一对 (a_i, b_i) 都不连通。
bool check_after_cut(int cut) {
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= n - 1; i++) {
        if (i == cut) continue; // 这条边被砍掉了，不参与合并
        int ru = find_root(eu[i]);
        int rv = find_root(ev[i]);
        if (ru != rv) fa[ru] = rv;
    }
    for (int i = 1; i <= m; i++) {
        if (find_root(qa[i]) == find_root(qb[i])) return false; // 还有连通的点对
    }
    return true;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n - 1; i++) {
        cin >> eu[i] >> ev[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> qa[i] >> qb[i];
    }

    int ans = -1;
    for (int cut = 1; cut <= n - 1; cut++) {
        if (check_after_cut(cut)) ans = cut; // 编号递增，最后留下的就是最大编号
    }

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

复杂度

枚举 $n-1$ 条边，每次重建并查集需要 $O(n \alpha(n))$ ，总时间复杂度 $O(n^2 \alpha(n))$ ，空间复杂度 $O(n)$ 。

瓶颈

瓶颈是“每换一条边就把整棵树重新合并一次”。 $n = 10^5$ 时这个做法要合并 $10^{10}$ 量级的边，完全不可行。之所以浪费，是因为砍不同的边时，绝大多数路径的形态是不变的，但我们每次都重新判定了一遍。要打破这个瓶颈，就要把 $n-1$ 种砍法一次性处理掉。

正解

思路

第一步：把“能否分开”翻译成“路径是否跨过这条边”

a_i, b_i \text{ 被分开} \iff \text{被砍的边在 } a_i \to b_i \text{ 的唯一路径上}

这个等价是整道题的支点。它把“删边以后检查连通性”这个要跑 $n$ 次的动态过程，变成了每条边上的一个静态计数：

记 $cnt(e)$ 为“路径经过边 $e$ ”的数对个数。答案就是所有满足 $cnt(e) = m$ 的边中编号最大的那条。

因为 $(a_i, b_i)$ 只有 $m$ 对， $cnt(e) = m$ 表示 $m$ 条路径全部跨过了 $e$ ；只要有一条不跨过，砍掉 $e$ 就分不开对应的那一对。

第二步：树边与“子树”一一对应

给树随便定一个根（取 $1$ 号点），对每个非根点 $u$ ，记它的父边为 $(u, par_u)$ 。砍掉这条边会把树分成两块：

$u$ 的子树里的点；
子树外的点。

一条路径跨过 $(u, par_u)$ 当且仅当它的两个端点恰有一个落在 $u$ 的子树内。于是：

$cnt(u, par_u) = $ 子树 $u$ 内“被路径端点选中”的标记和。

每个路径的两个端点 $a_i, b_i$ 都在自己所在的子树里留下一次标记，所以只要把“以 $u$ 为子树的所有标记”加起来，就能得到跨过父边的路径数。这一步把“路径”这个一维对象压成了“点权”这个零维对象，是能线性统计的关键。

第三步：用点差分一次性打标记

想直接给“某条路径经过的每条边都加一”是很贵的（一条路径可以长达 $O(n)$ ）。差分技巧的做法是：只在端点上做加减，让子树求和的自然过程去还原每条边上的真实值。

对每个数对 $(a_i, b_i)$ ，设 $w = \mathrm{LCA}(a_i, b_i)$ ，执行：

\mathrm{diff}[a_i] \mathrel{+}= 1,\qquad \mathrm{diff}[b_i] \mathrel{+}= 1,\qquad \mathrm{diff}[w] \mathrel{-}= 2.

为什么是 $-2$ ？因为从根往下看， $a_i$ 到 $b_i$ 的路径可以拆成 $a_i \to w$ 和 $b_i \to w$ 两段，两段的“顶端”都是 $w$ ：

对 $a_i$ 加 $1$ ，会让 $w$ 到根的整条链都多出 $1$ ，其中 $a_i \to w$ 这一段正是我们要的；
对 $b_i$ 加 $1$ ，同样会让 $b_i \to w$ 这一段多出 $1$ ；
但 $w$ 到根这一段被多加了两次，而这条路径根本没走到那里，所以要用 $\mathrm{diff}[w] -= 2$ 抵掉。

做完差分后，把每个点的值自底向上累加到父亲，累加结束后 $u$ 上的值就等于“跨过父边 $(u, par_u)$ 的路径数”，也就是 $cnt(u, par_u)$ 。

用样例里的 $(3,6)$ 和 $(4,5)$ 走一遍（根取 $1$ ， $w_1 = \mathrm{LCA}(3,6) = 2$ ， $w_2 = \mathrm{LCA}(4,5) = 2$ ）：

结点	1	2	3	4	5	6
$\mathrm{diff}$	0	$-4$	$+1$	$+1$	$+1$	$+1$
子树求和（= 父边被跨过次数）	—	0	1	1	1	1

对照输入编号：边 $1=(1,2)$ 对应 $cnt=0$ ，边 $2=(2,3)$ 对应 $cnt=1$ ，边 $3=(3,4)$ 对应 $cnt=1$ ，边 $4=(2,5)$ 对应 $cnt=1$ ，边 $5=(5,6)$ 对应 $cnt=1$ 。 $m=2$ 时只有编号 $2$ 和编号 $4$ 满足 $cnt=m$ ，取编号最大得 $4$ ，与样例一致。

第四步：LCA 与实现细节

$\mathrm{LCA}$ 用倍增求：先预处理 $up[j][u]$ 表示 $u$ 的第 $2^j$ 级祖先，然后先把深的点抬到同一深度，再一起往上跳。

两个实现上的边界值得注意：

不能写递归 DFS 求深度。 $n$ 可达 $10^5$ ，输入可以是一条链，深度就是 $10^5$ ，递归会爆系统栈。改成用 queue 做一次迭代 BFS，顺便得到“父亲一定排在儿子前面”的 bfs 序。
自底向上求和不走第二遍 DFS。把 bfs 序倒着扫一遍就是自底向上的顺序：处理到 $u$ 时，它的所有儿子都已经把自己的值推给了 $u$ ，于是 $\mathrm{diff}[u]$ 已经是最终值，直接记下来再推给父亲即可。
每条边归属哪个端点。编号为 $i$ 的边 $(x, y)$ 在根树上一定有且只有一个端点是另一个的父亲，那个端点就是要查 $cnt$ 的儿子点。
输出最大编号。按 $i = 1 \sim n-1$ 递增检查，每次满足条件就覆盖 ans，循环结束时留下的自然就是最大编号，不需要额外比较。

代码

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/**
 * 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-03 11:50
 * update_at: 2026-10-03 11:50
 */
// P9246 [蓝桥杯 2023 省 B] 砍树
// 思路：
//   1. 砍掉一条边以后树只剩两个连通块，所以一对 (a, b) 被砍开的充要条件是
//      “这条边在 a 到 b 的树上路径上”。于是每条边只需要一个信息：
//      有多少条给定路径跨过它；被全部 m 条路径跨过的边才是可行答案。
//   2. 砍掉边 (u, par[u]) 会把树分成 u 的子树和子树外两部分，
//      跨过它的路径数 cross[u] 恰好等于“子树内标记和”，用点差分一次求出：
//      对每条路径 (a, b) 做 diff[a] += 1、diff[b] += 1、diff[lca(a,b)] -= 2，
//      自底向上把子树内的标记加起来就是 cross[u]。
//   3. LCA 用倍增求；自底向上求和用 bfs 序倒扫代替递归，避免链状数据爆栈。
//   4. 按输入顺序扫一遍所有边，cross == m 就更新答案，最后留下的自然是最大编号。
#include <iostream>
using namespace std;

const int MAXN = 100005;
const int MAXE = 200005;
const int LOG = 18; // 2^17 > 1e5，足够表示任意深度差

int n, m;

int head[MAXN], nxt[MAXE], to[MAXE], ecnt; // 链式前向星存树
int eu[MAXN], ev[MAXN];                    // 第 i 条输入边的两个端点

int par[MAXN];          // par[u]：以 1 为根时 u 的父亲
int dep[MAXN];          // dep[u]：u 的深度，根的深度为 1
int ord[MAXN], ordcnt;  // bfs 序，父亲一定排在儿子前面
int up[LOG][MAXN];      // up[j][u]：u 的第 2^j 级祖先，倍增求 LCA
int diff[MAXN];         // 点差分标记：路径端点 +1、LCA -2
int cross_[MAXN];       // cross_[u]：跨过 (u, par[u]) 这条边的路径条数

// 加一条无向边
void add_edge(int u, int v) {
    ecnt++;
    to[ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
    ecnt++;
    to[ecnt] = u;
    nxt[ecnt] = head[v];
    head[v] = ecnt;
}

// 以 1 为根，用迭代 bfs 求父亲、深度、bfs 序，并建好倍增表。
// 不用递归 dfs 是因为 n 可以达到 1e5，链状数据会爆系统栈。
void build_tree() {
    int qh = 0, qt = 0;
    par[1] = 0;
    dep[1] = 1;
    ord[qt++] = 1;
    while (qh < qt) {
        int u = ord[qh++];
        for (int i = head[u]; i != 0; i = nxt[i]) {
            int v = to[i];
            if (v == par[u]) continue; // 树上除父亲外的邻居都是儿子
            par[v] = u;
            dep[v] = dep[u] + 1;
            ord[qt++] = v;
        }
    }
    ordcnt = qt;
    for (int v = 1; v <= n; v++) up[0][v] = par[v];
    // bfs 序保证父亲先于儿子，逐层递推即可
    for (int j = 1; j < LOG; j++) {
        for (int k = 0; k < ordcnt; k++) {
            int v = ord[k];
            up[j][v] = up[j - 1][up[j - 1][v]];
        }
    }
}

// 倍增求 LCA
int lca(int u, int v) {
    if (dep[u] < dep[v]) {
        int t = u;
        u = v;
        v = t;
    }
    int d = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++) {
        if ((d >> j) & 1) u = up[j][u];
    }
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) {
        if (up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    }
    return up[0][u];
}

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

    cin >> n >> m;
    for (int i = 1; i <= n - 1; i++) {
        cin >> eu[i] >> ev[i];
        add_edge(eu[i], ev[i]);
    }

    build_tree();

    // 读入 m 个数对，直接打成点差分标记
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        int w = lca(a, b);
        diff[a]++;
        diff[b]++;
        diff[w] -= 2;
    }

    // 逆 bfs 序累加子树标记：处理到 u 时，它的儿子都已经把值推给了 u
    for (int k = ordcnt - 1; k >= 0; k--) {
        int u = ord[k];
        cross_[u] = diff[u];
        if (u != 1) diff[par[u]] += diff[u];
    }

    // 依次检查每条边，编号递增所以最后记下的就是最大编号
    int ans = -1;
    for (int i = 1; i <= n - 1; i++) {
        int u = eu[i], v = ev[i];
        int child; // 这条边在 bfs 树上的儿子端点
        if (par[u] == v) {
            child = u;
        } else {
            child = v;
        }
        if (cross_[child] == m) ans = i;
    }

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

复杂度

BFS 与建倍增表都是 $O(n \log n)$ ；每个数对求一次 LCA 是 $O(\log n)$ ，共 $O(m \log n)$ ；差分打标记是 $O(m)$ ，自底向上求和与枚举边都是 $O(n)$ 。总时间复杂度 $O((n + m) \log n)$ ，空间复杂度 $O(n \log n)$ （主要是倍增表）。 $n = 10^5$ 时运行时间在毫秒级。

总结

这道题的难度不在数据结构，而在**把“删边后检查连通性”改写成“边被路径覆盖”**这一步：

树删一条边只剩两个连通块，所以分离一对点等价于把这条边放在它们的路径上；
于是要给每条边统计“被多少条路径覆盖”，答案就是覆盖数等于 $m$ 的边里编号最大的那条；
树上的“路径加、单点查”用点差分转成“端点加、子树求和”，配合 LCA 就能做到 $O((n+m)\log n)$ 。

差分的关键永远是先想清楚朴素做法在做哪种区间加法，再找能抵消重复部分的位置。这里重复的位置就是 $\mathrm{LCA}$ ，所以减去 $2$ 。写代码时再顺手处理掉两处 $O(n)$ 递归的爆栈隐患（求深度、求子树和），就能安全通过 $n = 10^5$ 的规模。

P9246 [蓝桥杯 2023 省 B] 砍树

题目描述

给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $\left(a_{1},b_{1}\right),\left(a_{2},b_{2}\right),\ldots,\left(a_{m},b_{m}\right)$ ，其中 $a_{i}$ 互不相同， $b_{i}$ 互不相同， $a_{i} \neq b_{j}(1 \leq i,j \leq m)$ 。

小明想知道是否能够选择一条树上的边砍断，使得对于每个 $\left(a_{i},b_{i}\right)$ 满足 $a_{i}$ 和 $b_{i}$ 不连通，如果可以则输出应该断掉的边的编号 (编号按输入顺序从 $1$ 开始)，否则输出 -1。

输入格式

输入共 $n+m$ 行，第一行为两个正整数 $n,m$ 。

后面 $n-1$ 行，每行两个正整数 $x_{i},y_{i}$ 表示第 $i$ 条边的两个端点。

后面 $m$ 行，每行两个正整数 $a_{i},b_{i}$ 。

输出格式

一行一个整数，表示答案，如有多个答案，输出编号最大的一个。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【样例说明】

断开第 $2$ 条边后形成两个连通块： $\{3,4\},\{1,2,5,6\}$ ，满足 $3$ 和 $6$ 不连通， $4$ 和 $5$ 不连通。

断开第 $4$ 条边后形成两个连通块： $\{1,2,3,4\},\{5,6\}$ ，同样满足 $3$ 和 $6$ 不连通， $4$ 和 $5$ 不连通。

$4$ 编号更大，因此答案为 $4$ 。

【评测用例规模与约定】

对于 $30 \%$ 的数据，保证 $1<n \leq 10^3$ 。

对于 $100 \%$ 的数据，保证 $1<n \leq 10^{5}$ ， $1 \leq m \leq \frac{n}{2}$ 。

蓝桥杯 2023 省赛 B 组 J 题。