GESP 题解库 / 8 级题解 / [GESP202503 八级] 割裂 · 第 9 / 24 题
GESP202503 八级 · P11967 · 困难

割裂

可删 ⟺ 在坏点对路径上,且不被任何好点对路径覆盖 —— 树上差分 + 子树和一次判完。

🌳
n ≤ 10⁶
结点数
🔗
a ≤ 10⁵
好点对个数
⚡
O((n + a) log n)
LCA + 差分
🎯
坏路径上且好路径覆盖数 = 0
核心判定
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。

小杨设置了 a 个好点对 {⟨u₁, v₁⟩, ⟨u₂, v₂⟩, …, ⟨u_a, v_a⟩} 和一个坏点对 ⟨b_u, b_v⟩。一个节点能被删除,当且仅当:

如果点对中的任意一个节点被删除,其视为不连通。

小杨想知道,还有多少个节点能被删除。

输入格式:第一行包含两个非负整数 n, a;接下来 n − 1 行,每行两个正整数 xᵢ, yᵢ,代表一条边;之后 a 行,每行两个正整数 uᵢ, vᵢ,代表一个好点对;最后一行包含两个正整数 b_u, b_v,代表坏点对。

输出格式:输出一个非负整数,代表删除的节点个数。

输入输出样例

输入输出
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
2

数据范围:1 ≤ n ≤ 10⁶,0 ≤ a ≤ 10⁵,uᵢ ≠ vᵢ,b_u ≠ b_v。子任务:20% 保证 n = 10 且 a = 0;20% n, a ≤ 100;60% n ≤ 10⁶, a ≤ 10⁵。

💡
人话翻译:删掉一个点 v 会把这棵树劈成deg(v) 块,于是两个点"连通"当且仅当它们落在同一块里。
但对树来说,有一个漂亮的一步结论:
· u, v 删掉 x 后仍连通 ⟺ x 不在 u → v 的唯一路径上;
· u, v 删掉 x 后不连通 ⟺ x 在 u → v 的路径上(含两个端点)。
(注意题目特意强调"点对中的任意一个节点被删除,视为不连通"——这就是"路径要含端点"的来源。)
于是答案就是:在坏点对路径上、且不被任何好点对路径覆盖的结点个数。
剩下的就是两个技术活:① 用 LCA 求出每条路径;② 用树上差分 + 子树和一次性统计"被多少条路径覆盖"。

🔍 关键词提取

树上路径判定LCA树上差分子树和被路径覆盖的结点

已知条件

项目说明
输入第一行 n, a;n − 1 条边;a 个好点对;1 个坏点对
输出能被删除的结点数(非负整数)
数据范围1 ≤ n ≤ 10⁶,0 ≤ a ≤ 10⁵
点对约束uᵢ ≠ vᵢ,b_u ≠ b_v
端点规则点对被删掉任一端点即视为不连通
子任务20%:n = 10 且 a = 0;20%:n, a ≤ 100;60%:n ≤ 10⁶, a ≤ 10⁵
工程要点n 到 10⁶:快读 + 迭代 DFS + 注意内存

需要解决的问题

02
思维导图
整理解题思路的全貌
✂️ 路径判定 + 树上差分覆盖计数
🧠 条件翻译
删 x 后 (u,v) 仍连通 ⟺ x 不在 path(u,v) 上
删 x 后不连通 ⟺ x 在 path(u,v) 上(含端点)
可删 ⟺ 在坏路径上 且 不在任何好路径上
端点被删也算断开 → 路径含两端
📐 路径覆盖计数
树上差分:D[u] += 1、D[v] += 1、D[L] −= 2
自底向上求子树和 S[x]
cntLca[x] = LCA 恰为 x 的点对数
x 被覆盖 ⟺ S[x] + cntLca[x] ≥ 1
🧮 得到答案
坏路径覆盖数 b[x] ∈ {0, 1}
好路径覆盖数 g[x](可 ≥ 2)
ans = #{x : b[x] = 1 且 g[x] = 0}
a = 0 时答案就是坏路径长度
⚠️ 易错点
忘了加 cntLca(LCA 那一点被漏掉)
把"含端点"漏掉(只统计中间点)
n = 10⁶ 用递归 DFS → 爆栈
不用快读 / 倍增表内存爆掉
03
样例手算推导
样例 1 逐点判定 + 差分数组完整手算

🧮 样例 1:先把路径画出来,再逐点判定

样例 1 的 5 条边是 1–3, 1–5, 3–6, 3–2, 5–4;好点对 (5, 4)、(5, 3);坏点对 (2, 6)。

点对类型唯一路径路径上的结点
⟨5, 4⟩好5 – 4{4, 5}
⟨5, 3⟩好5 – 1 – 3{1, 3, 5}
⟨2, 6⟩坏2 – 3 – 6{2, 3, 6}

逐个结点检查

结点 x在坏路径上?被好路径覆盖?能删除?
1否是(5–3 路径)❌
2是(端点)否✅ 删掉它,2 和 6 就断了
3是(中间点)是(5–3 路径)❌
4否是(5–4 路径)❌
5否是(两条好路径都含它)❌
6是(端点)否✅ 删掉它,2 和 6 就断了

答案 = 2 ✓

🔑
端点为什么一定要算进去?题目专门加了一句"如果点对中的任意一个节点被删除,其视为不连通"。
如果没有这句话,"删掉 2 之后 2 和 6 还连通吗"这个问题会变得含糊(2 都不存在了)。
加上这句话后,路径必须包含两个端点,于是 x 在坏路径上的判定就是"S_b[x] + cntLca_b[x] ≥ 1",端点自然被算进去(端点的子树和是 1)。

🧮 差分数组手算:把"覆盖数"一次算出来

以 1 为根,树的结构与深度如下:

结点父结点深度
1(根)0
311
511
232
632
452
1
好点对 ⟨5, 4⟩:LCA = 5

Dg[5] += 1、Dg[4] += 1、Dg[5] −= 2

净效果:Dg[5] = −1,Dg[4] = +1

cntLca_g[5] += 1

记录完毕

2
好点对 ⟨5, 3⟩:LCA = 1

Dg[5] += 1、Dg[3] += 1、Dg[1] −= 2

注意 5 又加了一次:Dg[5] = −1 + 1 = 0

cntLca_g[1] += 1

记录完毕

3
好路径的差分数组与子树和

Dg:1 号 = −2,3 号 = +1,4 号 = +1,其余为 0

自底向上累加:Sg[4] = 1;Sg[2] = 0;Sg[6] = 0

Sg[3] = Dg[3] + Sg[2] + Sg[6] = 1

Sg[5] = Dg[5] + Sg[4] = 0 + 1 = 1

Sg[1] = Dg[1] + Sg[3] + Sg[5] = −2 + 1 + 1 = 0

覆盖数 g[x] = Sg[x] + cntLca_g[x]:

g[1] = 0 + 1 = 1 ✓(在 5–3 上);g[3] = 1 + 0 = 1 ✓

g[4] = 1 ✓;g[5] = 1 + 1 = 2 ✓(两条好路径都含它)

g[2] = 0、g[6] = 0 ✓(没被任何好路径覆盖)

✅ 好路径覆盖数全部对上

4
坏点对 ⟨2, 6⟩:LCA = 3

Db[2] += 1、Db[6] += 1、Db[3] −= 2,cntLca_b[3] += 1

自底向上:Sb[6] = 1、Sb[2] = 1、Sb[3] = −2 + 1 + 1 = 0、Sb[1] = 0

b[x] = Sb[x] + cntLca_b[x]:

b[2] = 1 + 0 = 1 ✓;b[6] = 1 + 0 = 1 ✓;b[3] = 0 + 1 = 1 ✓

b[1] = 0、b[4] = 0、b[5] = 0 ✓(都不在坏路径上)

✅ 坏路径恰好覆盖 {2, 3, 6}

5
合并两个条件

找 b[x] = 1 且 g[x] = 0 的结点:

x = 2:b = 1,g = 0 → 可删 ✅

x = 3:b = 1,g = 1 → 被好路径保护 ❌

x = 6:b = 1,g = 0 → 可删 ✅

合计 2 个

✅ 答案 2

⚠️
为什么必须有 cntLca 这一项?差分 D[u] += 1, D[v] += 1, D[L] −= 2 会让 L 处的子树和被抵消掉:S[L] = 2 − 2 = 0。
但 L 本身当然在路径上!所以要让判定式再补上"L 恰好等于 x 的点对数",即 cntLca[x]。
漏掉它就会把每个 LCA 误判成"不在路径上",样例 1 里结点 1 和 3 会被算错成可删,答案变 4(正确是 2)。
04
解法对比
树上差分 + 倍增 LCA vs 逐点删点暴力 vs 欧拉序 ST 表 LCA

⚔️ 解法对比

🟢 树上差分 + 倍增 LCA(推荐) 推荐

每个点对做一次差分,自底向上求子树和,最后一遍扫描统计答案

  • 时间 O((n + a) log n)
  • 空间 O(n log n)(倍增表)
  • n = 10⁶、a = 10⁵ 时约 4 × 10⁷
  • 代码约 80 行(含快读)
💡
正确性来源:对单条路径,S[x] + cntLca[x] 的取值恰好是 0 / 1;对多条路径求和,得到的就是"覆盖 x 的路径条数"。
所以"好路径覆盖数 = 0"这一判断不需要任何额外假设,直接来自差分的线性性。

🟠 暴力枚举每个点删掉后判连通

删一个点,再从 b_u 出发 BFS,看到不到 b_v,同时检查所有好点对

  • 时间 O(n × (n + a))
  • n = 10⁶ 时约 10¹² 次
  • 只能过 n, a ≤ 100 的部分分
  • 代码约 40 行,好写
⚠️
它能拿到什么分:前两个子任务(n = 10, a = 0 与 n, a ≤ 100)共 40 分。
如果考场上推不出路径结论,这 40 分是稳妥的保底;但大子任务的 n = 10⁶ 必须靠差分。

📈 性能对比

方案复杂度结论
树上差分 + 倍增 LCAO((n + a) log n) ≈ 4 × 10⁷✅ 正解,能拿 100
暴力删点 + BFS 判连通O(n(n + a)) ≈ 10¹²❌ 只能拿 40 分
欧拉序 + ST 表 LCAO(1) 查询,但 ST 表约 2n log(2n) 个 int⚠️ n = 10⁶ 时约 168 MB,内存吃紧,倍增更稳
Tarjan 离线 LCA预处理 O(n α(n)),空间 O(n)✅ 省内存(约 30 MB),但实现更复杂
05
算法流程图
LCA 预处理 → 两套差分 → 子树和 → 统计答案
开始快读 n、a,用边表(head / nxt / to)建图从根 1 出发做迭代 DFS:求父结点、深度与先序序列合成倍增表 up[j][x],用于 O(log n) 求 LCA逐个处理 a 个好点对 ⟨u, v⟩求 L = LCA(u, v);Dg[u] += 1、Dg[v] += 1、Dg[L] −= 2、cntLca_g[L] += 1a 个好点对都处理完了吗?坏点对同样做一次差分:Db、cntLca_b按先序倒序把子树的 D 累加到父结点,得到 S[x]Sb[x] + cntLca_b[x] ≥ 1 吗?是 ✓x 在坏路径上,继续看覆盖否 ✗x 不能删,跳过Sg[x] + cntLca_g[x] 等于 0 吗?是 ✓答案 +1否 ✗被好路径保护输出可删除的结点个数取下一个好点对
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

✂️ 割裂判定器(暴力走路径,直观对照公式)

按题目格式输入:第一行 n a,随后 n − 1 行边,随后 a 行好点对,最后一行坏点对。程序会直接枚举每条路径上的结点,逐点给出"在坏路径上 / 被好路径覆盖"的判定。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(快读 + 迭代 DFS + 倍增 LCA + 树上差分)

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000005;     // n ≤ 10^6
const int LOG  = 20;          // 2^20 = 1048576 > 10^6

// ---------- 快读(n = 10^6,必须用) ----------
static char ibuf[1 << 16];
static int  ilen = 0, ipos = 0;
inline char gc() {
    if (ipos == ilen) { ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin); ipos = 0; if (ilen <= 0) return 0; }
    return ibuf[ipos++];
}
inline int readInt() {
    char c = gc();
    while (c && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return x;
}

// ---------- 边表(比 vector 更省内存) ----------
int head[MAXN], nxt[2 * MAXN], to[2 * MAXN], ec = 0;
inline void addEdge(int u, int v) {
    to[ec] = v; nxt[ec] = head[u]; head[u] = ec++;
    to[ec] = u; nxt[ec] = head[v]; head[v] = ec++;
}

int par[MAXN], dep[MAXN], ord[MAXN];
int up[LOG][MAXN];
static int Dg[MAXN], Lg[MAXN], Db[MAXN], Lb[MAXN];
static int stk[MAXN];
static char vis[MAXN];

inline int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int d = dep[u] - dep[v];
    for (int j = 0; d; j++, d >>= 1)
        if (d & 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() {
    int n = readInt(), a = readInt();
    for (int i = 1; i <= n; i++) head[i] = -1;
    for (int i = 1; i < n; i++) { int x = readInt(), y = readInt(); addEdge(x, y); }

    // ---------- 迭代 DFS:父结点、深度、先序序列 ----------
    int cnt = 0, top = 0;
    par[1] = 1; dep[1] = 0; vis[1] = 1; stk[top++] = 1;
    while (top) {
        int u = stk[--top];
        ord[++cnt] = u;
        for (int e = head[u]; e != -1; e = nxt[e]) {
            int v = to[e];
            if (!vis[v]) { vis[v] = 1; par[v] = u; dep[v] = dep[u] + 1; stk[top++] = v; }
        }
    }

    for (int i = 1; i <= n; i++) up[0][i] = par[i];
    for (int j = 1; j < LOG; j++)
        for (int i = 1; i <= n; i++)
            up[j][i] = up[j-1][ up[j-1][i] ];

    // ---------- 好点对:差分 + LCA 计数 ----------
    for (int i = 0; i < a; i++) {
        int u = readInt(), v = readInt();
        int L = lca(u, v);
        Dg[u]++; Dg[v]++; Dg[L] -= 2; Lg[L]++;
    }
    // ---------- 坏点对 ----------
    int bu = readInt(), bv = readInt();
    int L = lca(bu, bv);
    Db[bu]++; Db[bv]++; Db[L] -= 2; Lb[L]++;

    // ---------- 子树和:倒着扫"先序序列"即可(结点先于其后代出现) ----------
    for (int i = cnt; i >= 1; i--) {
        int u = ord[i];
        if (u != 1) { Dg[par[u]] += Dg[u]; Db[par[u]] += Db[u]; }
    }

    // ---------- 统计答案 ----------
    int ans = 0;
    for (int x = 1; x <= n; x++) {
        bool onBad = (Db[x] + Lb[x]) >= 1;
        bool protec = (Dg[x] + Lg[x]) >= 1;
        if (onBad && !protec) ans++;
    }
    printf("%d\n", ans);
    return 0;
}
🔑
四个要点:① 快读:n = 10⁶ 时输入约 20 MB,cin/cout 会拖后腿,fread + 手写解析最稳;② 迭代 DFS:树可能是一条 10⁶ 深的链,递归直接爆栈(用一个全局 stk 数组即可);③ 倒扫先序序列就能做子树和:先序里结点一定排在它所有后代之前,倒过来扫就是"儿子先于父亲";④ Dg[x] + Lg[x] ≥ 1 里的 Lg 不能省——差分把 LCA 抵消成 0,要靠它补回来。

📖 关键几行怎么看

代码作用为什么这样写
while (top) { int u = stk[--top]; ... }迭代 DFS避免递归爆栈(链状数据深 10⁶)
up[j][i] = up[j-1][ up[j-1][i] ];倍增表O(n log n) 预处理,之后每次 LCA 只要 O(log n)
Dg[u]++; Dg[v]++; Dg[L] -= 2;树上差分路径上每点的"被覆盖"信号,等价于子树和
Lg[L]++;LCA 计数补回被 −2 抵消掉的 LCA 那一点
for (int i = cnt; i >= 1; i--)子树和倒扫先序 = 自底向上累加
if (onBad && !protec) ans++;统计两个条件同时满足才算可删
⚠️
五个坑:① 忘记 Lg[L]++(LCA 被漏掉,样例 1 会算成 4 而不是 2);② 把"被好路径覆盖"判成"被好路径部分覆盖"——必须任意一条好路径覆盖就不合法;③ 递归 DFS 处理链状数据(RE);④ 不用快读(n = 10⁶ 时 TLE);⑤ 倍增表开太小(LOG 至少要 20 才能覆盖 10⁶)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
2题面样例(坏路径 {2,3,6},3 被好路径保护)
4 0
1 2
1 3
1 4
2 3
3a = 0:没有好路径,坏路径上 3 个点全可删
5 0
1 2
2 3
3 4
4 5
1 5
5a = 0 且坏点对是链的两端:5 个点全可删
5 1
1 2
2 3
3 4
4 5
2 4
1 5
2好路径 {2,3,4} 保护了中间三点,只剩两端点 1、5 可删
5 1
1 2
2 3
3 4
4 5
1 5
1 5
0好点对与坏点对完全相同:谁也不能删
2 0
1 2
1 2
2n = 2 的最小情形:两个点都可删
10 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 7
5n = 10、a = 0 的子任务:坏路径 3–7 共 5 个点
✅
自查清单:① 有 Lg[L]++ 吗?② 判定式是 Sb + Lb ≥ 1 且 Sg + Lg = 0 吗?③ DFS 是迭代的吗?④ 快读和 LOG = 20 都到位了吗?

🚨 易错点清单

⚠️
漏掉 cntLca:差分把 LCA 处的子树和抵消成 0,不加 cntLca[x] 会把每个 LCA 误判成"不在路径上"。
⚠️
忘了端点:题目明确"点对中任意一个节点被删除视为不连通",所以路径要包含两端点,统计时别只数中间点。
⚠️
递归 DFS:n = 10⁶ 且可能是深链,必须迭代(用显式栈)。
⚠️
慢输入输出:n = 10⁶ 的输入约 20 MB,要 fread 快读,输出虽只有一个数但也别用 endl。
⚠️
倍增表太小:LOG 至少要 20(2²⁰ = 1048576 > 10⁶),开到 18 会在深链上跳不到位。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((n + a) log n)
空间复杂度
O(n log n)
预处理
n log n ≈ 2 × 10⁷ 次赋值
LCA / 移动
每次 ≤ 20 步

时间怎么算的?

空间都用在哪?

倍增表 up[20][10⁶] 占 20 × 10⁶ × 4 B = 80 MB;边表 head + nxt + to 约 (1 + 2 + 2) × 10⁶ × 4 B ≈ 20 MB;再加上父结点、深度、先序与四张差分数组,合计约 130 MB,在 256 MB 限制内。若内存更紧,可换成 Tarjan 离线 LCA(并查集),把 LCA 部分降到 O(n)。

✅ 约四千万次基础操作,1 秒时限对 C++ 来说足够。本题的真正门槛是"把删点连通性翻译成路径覆盖",以及 n = 10⁶ 下的工程细节(快读、迭代、内存)。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 「树上路径覆盖计数」通用模板(树上差分 + 子树和)
// 对每条路径 (u, v),设 L = LCA(u, v):
//     D[u] += 1;  D[v] += 1;  D[L] -= 2;  cntLca[L] += 1;
// 全部路径处理完后,自底向上求子树和 S[x]:
//     S[par[x]] += S[x]
// 则 x 被路径覆盖 ⟺ S[x] + cntLca[x] >= 1
//                   (S[x] 是"端点贡献 − 2 × LCA 贡献",
//                     再加回"LCA 恰为 x"的对数)
//
// 与之对称的"边被路径覆盖"版本:
//     D[u] += 1;  D[v] += 1;  D[L] -= 2;      // 只需这一行
// 边 x--par[x] 被覆盖 ⟺ S[x] >= 1(不需要 cntLca,因为 LCA 不影响任何边的计数)
//
// 迭代 DFS 求父结点/深度(防爆栈):
//     par[1] = 1; dep[1] = 0; vis[1] = 1; stk[top++] = 1;
//     while (top) { int u = stk[--top]; ord[++cnt] = u;
//         for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e];
//             if (!vis[v]) { vis[v] = 1; par[v] = u; dep[v] = dep[u] + 1; stk[top++] = v; } } }
//     倒扫 ord[] 就是自底向上(先序的逆序 = 后代先于祖先)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
树上的"删点连通性"删 x 后 u,v 不连通 ⟺ x 在 path(u,v) 上(含端点)割点、桥、树上连通性类问题
树上差分 + 子树和D[u]++、D[v]++、D[L]−=2 后求子树和统计"每条边/每个点被多少条路径经过",是树上路径统计的标准工具
cntLca 修正点版本要补回被 −2 抵消的 LCA所有"点被路径覆盖"的题都必须注意这一项
迭代 DFS + 先序逆序避免爆栈,同时天然得到自底向上的处理顺序所有 n ≥ 10⁵ 的树上统计题
快读 + 边表n = 10⁶ 时省内存、提速大输入的量级题(10⁶ 级)通用工程模板
🌟
思考题:如果把条件改成"删掉一条边后所有好点对仍连通、坏点对不连通",答案会怎么变?(提示:那就变成边的版本:x 对应边 (x, par[x]),差分只需 D[u] += 1, D[v] += 1, D[L] −= 2,不需要 cntLca,因为路径的 LCA 不会"落在某条边上"被抵消。
再想想:如果好点对要求是"删掉后仍然同属一个连通块",和本题"仍然连通"完全等价吗?把"点"换成"边"、把"覆盖"想清楚,这类题就一通百通。)