割裂 题解

题目分析

题目给定一棵 (n) 个节点的树，以及 (a) 个好点对和 (1) 个坏点对。一个节点能被删除当且仅当删除它之后：

• 所有好点对仍然连通；
• 坏点对不连通。

特别地，如果点对中某个节点被删除，该点对视为不连通。

由于是在树上，任意两点之间有且仅有一条简单路径。因此：

• 若要删除某节点 (x) 后好点对 ((u_i, v_i)) 依然连通，则 (x) 不能位于 (u_i) 到 (v_i) 的路径上（也不能是端点）。
• 若要删除某节点 (x) 后坏点对 ((b_u, b_v)) 不连通，则 (x) 必须位于 (b_u) 到 (b_v) 的路径上（或为端点）。

综上，能被删除的节点恰是那些在坏点对路径上，却不在任何一个好点对路径上的节点。

解题思路

需要快速处理树上路径覆盖问题，统计每个节点被多少条好点对路径覆盖，以及是否被坏点对路径覆盖。可以使用 最近公共祖先 (LCA) + 树上点差分 技巧。

对于一条 (u) 到 (v) 的路径，设 (p = \text{LCA}(u, v))，则路径覆盖可以通过差分数组操作实现：

• 在 (u) 处 (+1)，在 (v) 处 (+1)；
• 在 (p) 处 (-1)，在 (p) 的父节点处 (-1)。

完成所有路径的差分操作后，自底向上做子树求和，就能得到每个节点被多少条路径覆盖。

对 (a) 个好点对使用一个差分数组 g，对坏点对使用另一个差分数组 h。最终：

• g[x] 表示节点 (x) 被多少个好点对路径覆盖；
• h[x] 表示节点 (x) 被坏点对路径覆盖（如果 (h[x]>0) 则在路径上，否则不在）。

节点可删除的条件：g[x] == 0 且 h[x] > 0。

算法详细步骤

1. 建图：读入 (n, a) 和树边，邻接表存树。
2. 预处理 LCA：通过一次 DFS 计算每个节点深度以及倍增表 f[u][i]，用于高效求最近公共祖先。
3. 好点对差分：对每对 ((u_i, v_i))，求 LCA，执行 g[u]++, g[v]++, g[lca]--, g[parent(lca)]--。
4. 坏点对差分：对 ((b_u, b_v)) 做同样操作，记录在 h 数组。
5. 求和统计：第二次 DFS 自底向上将子节点的 g、h 累加到父节点，得到每个点真实的覆盖次数。
6. 计数：遍历所有节点，若 g[x] == 0 且 h[x] > 0，则答案加一。

时间复杂度分析

• 第一次 DFS（LCA 预处理）：(O(n \log n))。
• 对于 (a) 个好点对和 (1) 个坏点对，每次求 LCA 为 (O(\log n))，总复杂度 (O((a+1) \log n))。
• 第二次 DFS 求和：(O(n))。
• 总体时间复杂度 (O((n + a) \log n))，空间复杂度 (O(n \log n + n))。

在 (n \le 10^6)、(a \le 10^5) 的数据范围下，需要比较高效的实现（注意 1e6 的递归可能导致栈溢出，在部分环境需手工扩栈或使用迭代 DFS；参考代码采用递归，通常需要在评测环境中开启栈空间或使用非递归写法）。

参考代码及解释

以下是完整代码及详细注释。代码基于树上差分和倍增 LCA 实现。注意在统计答案时，正确条件应为 g[u] == 0 && h[u] > 0（即好点对路径不覆盖、坏点对路径覆盖）。原题给的代码片段中若出现 g[u] && h[u]，应理解为笔误，以下给出修正后的正确版本。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 1e6 + 10;
5int n, a;
6vector<int> e[N];
7int f[N][25], dep[N];
8int g[N], h[N];   // g: 好点对覆盖次数, h: 坏点对覆盖次数
9
10// 第一次 DFS：求深度与倍增 LCA
11void dfs(int u, int fa) {
12    dep[u] = dep[fa] + 1;
13    f[u][0] = fa;
14    for (int i = 1; i < 20; i++) {
15        f[u][i] = f[f[u][i-1]][i-1];
16    }
17    for (auto v : e[u]) {
18        if (v == fa) continue;
19        dfs(v, u);
20    }
21}
22
23// LCA 查询
24int lca(int u, int v) {
25    if (dep[u] < dep[v]) swap(u, v);
26    int t = dep[u] - dep[v];
27    for (int i = 0; i < 20; i++) {
28        if (t & (1 << i)) u = f[u][i];
29    }
30    if (u == v) return u;
31    for (int i = 19; i >= 0; i--) {
32        if (f[u][i] != f[v][i]) {
33            u = f[u][i];
34            v = f[v][i];
35        }
36    }
37    return f[u][0];
38}
39
40int ans;
41
42// 第二次 DFS：自底向上累加差分，并统计答案
43void dfs2(int u, int fa) {
44    for (auto v : e[u]) {
45        if (v == fa) continue;
46        dfs2(v, u);
47        g[u] += g[v];
48        h[u] += h[v];
49    }
50    // 能被删除的条件：没有任何好点对经过，且有坏点对经过
51    if (g[u] == 0 && h[u] > 0) {
52        ans++;
53    }
54}
55
56void solve() {
57    cin >> n >> a;
58    for (int i = 1; i < n; i++) {
59        int u, v;
60        cin >> u >> v;
61        e[u].push_back(v);
62        e[v].push_back(u);
63    }
64
65    dfs(1, 0);   // 预处理 LCA，根节点可任选（这里选 1）
66
67    // 好点对差分
68    for (int i = 1; i <= a; i++) {
69        int u, v;
70        cin >> u >> v;
71        int lc = lca(u, v);
72        g[u]++; g[v]++;
73        g[lc]--;
74        if (f[lc][0]) g[f[lc][0]]--;  // 注意根节点的父节点为 0，需判空
75    }
76
77    // 坏点对差分
78    int bu, bv;
79    cin >> bu >> bv;
80    int lc = lca(bu, bv);
81    h[bu]++; h[bv]++;
82    h[lc]--;
83    if (f[lc][0]) h[f[lc][0]]--;
84
85    dfs2(1, 0);
86    cout << ans << '\n';
87}
88
89int main() {
90    ios::sync_with_stdio(false);
91    cin.tie(nullptr);
92    solve();
93    return 0;
94}

代码细节说明

• LCA 部分：使用倍增法预处理 f[u][i] 表示 (u) 向上 (2^i) 步的祖先，方便路径差分时定位最近公共祖先。循环中 i 的范围根据 (n \le 10^6) 需要至少 21，这里取 20/25 均可。
• 差分操作：在 (u, v) 加 1，在 lca 减 1，在 lca 的父亲减 1。这样自底向上求和后，路径上的点净增 1，其余点为 0。注意处理 lca 为根节点时，其父亲为 0，需避免对 0 操作。
• 答案统计：g[u] == 0 保证删除该节点后所有好点对保持连通；h[u] > 0 保证坏点对变为不连通。满足两个条件则该节点可删。

易错点

• 树上差分时一定要在 lca 和其父亲两处做减法，否则求和后路径顶端会多算。
• 递归深度可能达到 (n)，在 (10^6) 规模下注意防止栈溢出（可以通过编译参数 -Wl,-stack,16777216 或使用迭代栈实现 DFS）。
• 好点对可能有重复，或与坏点对重合，差分数组求和仍能正确处理。

通过上述算法，我们能够在 (O((n+a)\log n)) 时间内求出所有可以删除的节点个数。