可删 ⟺ 在坏点对路径上,且不被任何好点对路径覆盖 —— 树上差分 + 子树和一次判完。
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n。
小杨设置了 a 个好点对 {⟨u₁, v₁⟩, ⟨u₂, v₂⟩, …, ⟨u_a, v_a⟩} 和一个坏点对 ⟨b_u, b_v⟩。一个节点能被删除,当且仅当:
1 ≤ i ≤ a,好点对 uᵢ 和 vᵢ 仍然连通;b_u 和 b_v 不连通。如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,还有多少个节点能被删除。
输入格式:第一行包含两个非负整数 n, a;接下来 n − 1 行,每行两个正整数 xᵢ, yᵢ,代表一条边;之后 a 行,每行两个正整数 uᵢ, vᵢ,代表一个好点对;最后一行包含两个正整数 b_u, b_v,代表坏点对。
输出格式:输出一个非负整数,代表删除的节点个数。
输入输出样例
| 输入 | 输出 |
|---|---|
6 2 | 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树上差分子树和被路径覆盖的结点
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 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 + 注意内存 |
x 不在任何好路径上"?只要有一条好点对因为 x 被删而断开,x 就不合法;所以是"所有好路径都不覆盖 x"x 被多少条路径覆盖"?逐条路径去染色是 O(a·n)(最坏 10¹¹),必须用树上差分:对路径 (u, v),令 D[u] += 1, D[v] += 1, D[LCA] −= 2,然后自底向上求子树和 S[x]cntLca[x]?差分把路径两端的贡献都算上了,但 LCA 那一点被 −2 抵消掉了;而 LCA 明明在路径上,所以要单独记 cntLca[x] = "LCA 恰好为 x 的点对数",判定式是 S[x] + cntLca[x] ≥ 1S[x] + cntLca[x] 的取值只可能是 0 或 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 ✓
x 在坏路径上的判定就是"S_b[x] + cntLca_b[x] ≥ 1",端点自然被算进去(端点的子树和是 1)。以 1 为根,树的结构与深度如下:
| 结点 | 父结点 | 深度 |
|---|---|---|
| 1 | (根) | 0 |
| 3 | 1 | 1 |
| 5 | 1 | 1 |
| 2 | 3 | 2 |
| 6 | 3 | 2 |
| 4 | 5 | 2 |
Dg[5] += 1、Dg[4] += 1、Dg[5] −= 2
净效果:Dg[5] = −1,Dg[4] = +1
cntLca_g[5] += 1
记录完毕
Dg[5] += 1、Dg[3] += 1、Dg[1] −= 2
注意 5 又加了一次:Dg[5] = −1 + 1 = 0
cntLca_g[1] += 1
记录完毕
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 ✓(没被任何好路径覆盖)
✅ 好路径覆盖数全部对上
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}
找 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]。每个点对做一次差分,自底向上求子树和,最后一遍扫描统计答案
S[x] + cntLca[x] 的取值恰好是 0 / 1;对多条路径求和,得到的就是"覆盖 x 的路径条数"。删一个点,再从 b_u 出发 BFS,看到不到 b_v,同时检查所有好点对
n, a ≤ 100 的部分分n = 10, a = 0 与 n, a ≤ 100)共 40 分。n = 10⁶ 必须靠差分。| 方案 | 复杂度 | 结论 |
|---|---|---|
| 树上差分 + 倍增 LCA | O((n + a) log n) ≈ 4 × 10⁷ | ✅ 正解,能拿 100 |
| 暴力删点 + BFS 判连通 | O(n(n + a)) ≈ 10¹² | ❌ 只能拿 40 分 |
| 欧拉序 + ST 表 LCA | O(1) 查询,但 ST 表约 2n log(2n) 个 int | ⚠️ n = 10⁶ 时约 168 MB,内存吃紧,倍增更稳 |
| Tarjan 离线 LCA | 预处理 O(n α(n)),空间 O(n) | ✅ 省内存(约 30 MB),但实现更复杂 |
按题目格式输入:第一行 n a,随后 n − 1 行边,随后 a 行好点对,最后一行坏点对。程序会直接枚举每条路径上的结点,逐点给出"在坏路径上 / 被好路径覆盖"的判定。
点按钮开始 →
#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; }
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⁶)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 2 | 2 | 题面样例(坏路径 {2,3,6},3 被好路径保护) |
4 0 | 3 | a = 0:没有好路径,坏路径上 3 个点全可删 |
5 0 | 5 | a = 0 且坏点对是链的两端:5 个点全可删 |
5 1 | 2 | 好路径 {2,3,4} 保护了中间三点,只剩两端点 1、5 可删 |
5 1 | 0 | 好点对与坏点对完全相同:谁也不能删 |
2 0 | 2 | n = 2 的最小情形:两个点都可删 |
10 0 | 5 | n = 10、a = 0 的子任务:坏路径 3–7 共 5 个点 |
Lg[L]++ 吗?② 判定式是 Sb + Lb ≥ 1 且 Sg + Lg = 0 吗?③ DFS 是迭代的吗?④ 快读和 LOG = 20 都到位了吗?cntLca:差分把 LCA 处的子树和抵消成 0,不加 cntLca[x] 会把每个 LCA 误判成"不在路径上"。fread 快读,输出虽只有一个数但也别用 endl。LOG 至少要 20(2²⁰ = 1048576 > 10⁶),开到 18 会在深链上跳不到位。LOG × n = 20 × 10⁶ = 2 × 10⁷ 次赋值(a + 1) × 20 ≈ 2 × 10⁶倍增表 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⁶ 下的工程细节(快读、迭代、内存)。
// 「树上路径覆盖计数」通用模板(树上差分 + 子树和) // 对每条路径 (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 不会"落在某条边上"被抵消。