P9246 [蓝桥杯 2023 省 B] 砍树-题解（最近公共祖先LCA + 树上差分）

一、题目描述

给定一棵由 $n$ 个节点组成的树和 $m$ 个无序数对 $(a_i,b_i)$，要求找到一条边，使得砍断这条边后，所有数对中的两个节点都不连通。若存在多条满足条件的边，输出编号最大的；否则输出 -1。

二、题目分析

暴力实现思路

1. 枚举每条边：尝试删除每条边，检查是否满足所有数对不连通
2. 连通性检查：对每个数对使用DFS/BFS检查连通性
3. 时间复杂度：$O(m\times n^2)$，只能通过30%数据

正解思路

1. 关键观察：满足条件的边必须被所有数对的路径覆盖
2. 高效统计：使用树上差分快速统计每条边被路径覆盖的次数
3. 算法选择：LCA（最近公共祖先）+ 树上差分

三、解题思路 + 算法介绍

1. LCA预处理

• 倍增法预处理每个节点的 $2^k$ 级祖先
• 支持 $O(\log n)$ 时间查询任意两节点的LCA

2. 树上差分

• 边差分：将边权下放到子节点
• 对每个数对 $(a_i,b_i)$：
  • diff[a_i]++, diff[b_i]++（路径端点标记）
  • diff[lca(a_i, b_i)] -= 2（消除LCA以上影响）

3. 统计覆盖次数

• DFS后序遍历累加差分值
• diff[v] 表示边 $u\to v$ 被覆盖的次数

四、代码实现

暴力代码（30分）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> path;
int w[N], h[N], e[N<<1], ne[N<<1], idx;void add(int a, int b) { e[idx]=b, ne[idx]=h[a], h[a]=idx++; }bool dfs(int u, int fa, int v) {if (u == v) return true;for (int i = h[u]; ~i; i = ne[i]) {int j = e[i];if (j == fa) continue;path.push_back(i/2 + 1);if (dfs(j, u, v)) return true;path.pop_back();}return false;
}int main() {memset(h, -1, sizeof h);int n, m; cin >> n >> m;for (int i = 1; i < n; i++) {int a, b; cin >> a >> b;add(a, b), add(b, a);}for (int i = 0; i < m; i++) {int a, b; cin >> a >> b;path.clear();dfs(a, -1, b);for (int e : path) w[e]++;}int ans = -1;for (int i = n-1; i >= 1; i--)if (w[i] == m) { ans = i; break; }cout << ans;
}

正解代码（100分）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, diff[N], depth[N], f[N][20], cnt[N], ans = -1;
int h[N], e[N<<1], ne[N<<1], id[N<<1], idx;void add(int a, int b, int c) { e[idx]=b, id[idx]=c, ne[idx]=h[a], h[a]=idx++; }void bfs() {memset(depth, 0x3f, sizeof depth);queue<int> q; q.push(1); depth[1] = 1;while (q.size()) {int u = q.front(); q.pop();for (int i = h[u]; ~i; i = ne[i]) {int v = e[i];if (depth[v] > depth[u] + 1) {depth[v] = depth[u] + 1;f[v][0] = u;for (int k = 1; k < 20; k++)f[v][k] = f[f[v][k-1]][k-1];q.push(v);}}}
}int lca(int a, int b) {if (depth[a] < depth[b]) swap(a, b);for (int k = 19; k >= 0; k--)if (depth[f[a][k]] >= depth[b])a = f[a][k];if (a == b) return a;for (int k = 19; k >= 0; k--)if (f[a][k] != f[b][k])a = f[a][k], b = f[b][k];return f[a][0];
}void dfs(int u, int fa) {for (int i = h[u]; ~i; i = ne[i]) {int v = e[i];if (v == fa) continue;dfs(v, u);diff[u] += diff[v];if (id[i] != -1 && diff[v] == m)ans = max(ans, id[i]);}
}int main() {memset(h, -1, sizeof h);cin >> n >> m;for (int i = 1; i < n; i++) {int a, b; cin >> a >> b;add(a, b, i), add(b, a, i);}bfs();for (int i = 0; i < m; i++) {int a, b; cin >> a >> b;diff[a]++, diff[b]++;diff[lca(a, b)] -= 2;}dfs(1, -1);cout << ans;
}

五、重点细节

1. 边编号处理：
   • 无向边存储两次，通过 id[i] 避免重复统计
   • i/2 + 1 将邻接表索引转为边编号
2. 差分还原：
   • DFS后序遍历确保先处理子树
   • diff[v] 直接表示边 $u\to v$ 的覆盖次数
3. LCA优化：
   • 使用BFS初始化避免递归栈溢出
   • 哨兵节点 depth[0] = 0 处理边界

六、复杂度分析

算法	时间复杂度	空间复杂度
暴力	$O(m{n}^2)$	$O(n)$
正解	$O(n\log n)$	$O(n\log n)$

七、总结

1. 暴力法：简单直观但效率低，适用于小数据
2. 正解法：
   • 利用LCA快速定位路径
   • 树上差分高效统计覆盖次数
   • 完美结合树结构的递归特性
3. 关键技巧：边权下放、差分标记、后序统计
4. 适用场景：需要高效处理树上路径覆盖统计的问题