当前位置：首页 > news >正文

[蓝桥杯]真题剖析：砍树（从暴力DFS到树上差分+LCA的算法演进）

news 2026/6/29 8:19:36

1. 从暴力DFS到树上差分：砍树问题的算法演进

第一次看到蓝桥杯这道砍树题目时，我和大多数选手一样，第一反应就是用DFS暴力搜索。题目大意是给定一棵树和若干路径，要求找到满足所有路径都经过的边中编号最大的那条。直接思路很直观：对于每条路径，用DFS标记经过的边，最后统计被标记m次的边。

我写的第一个版本和题目给出的暴力代码几乎一模一样。这个解法虽然直观，但当树节点数N=1e5，路径数M=1e5时，时间复杂度直接飙到O(M*N)。在本地测试时，当N和M都超过1e4，程序就开始卡顿了。这时候我意识到，必须寻找更高效的算法。

2. 暴力DFS的瓶颈分析与优化方向

2.1 暴力解法的时间复杂度分析

暴力DFS的瓶颈在于处理每条路径时都要完整遍历一次树。假设树退化成链，最坏情况下每次DFS都是O(N)复杂度，M次查询就是O(M*N)。这在N和M都是1e5量级时，总运算次数会达到1e10，远远超出时间限制。

2.2 图的存储优化

在优化之前，我们先看看如何高效存储树结构。题目给出的邻接表存储方式（vector edge[N]）已经是比较高效的方式了。不过在实际编码时，我发现用pair记录边的编号有些繁琐，可以改用结构体存储边信息：

struct Edge { int to, id; }; vector<Edge> edge[N];

这样在DFS时可以直接获取边的编号，省去了map查询的开销。虽然这不能改变时间复杂度，但在实际运行中能减少常数时间。

3. 树上差分：从O(MN)到O(M+N)的飞跃

3.1 差分数组的思想迁移

差分是处理区间修改的高效技巧。在一维数组中，要给区间[l,r]统一加1，我们只需要在l位置+1，r+1位置-1，最后通过前缀和就能还原出每个位置的值。

将这个思想迁移到树上，就形成了树上差分。对于树上的路径u-v，我们可以将其拆分为u->LCA(u,v)和v->LCA(u,v)两条链，然后在u和v处+1，在LCA(u,v)处-2。

3.2 实现树上差分

具体实现需要三个步骤：

预处理出每个节点的父节点和深度（DFS或BFS）
对于每条路径u-v，找到它们的LCA
在u和v处+1，在LCA处-2
最后通过后序遍历计算子树和

核心代码片段：

void cal_sum(int u, int father) { for(auto &e : edge[u]) { if(e.to == father) continue; cal_sum(e.to, u); w[u] += w[e.to]; } }

这个优化将时间复杂度降到了O(M+N)，完全能够处理1e5量级的数据。

4. LCA算法选择与实现

4.1 为什么需要LCA

在树上差分中，LCA（最近公共祖先）是关键。我们需要快速找到任意两个节点的LCA，才能正确应用差分标记。暴力找LCA的方法（交替向上爬）在最坏情况下是O(N)复杂度，这又可能使总复杂度退化为O(MN)。

4.2 倍增法实现LCA

倍增法是一种常见的LCA算法，通过预处理每个节点向上2^k层的祖先，可以在O(logN)时间内找到LCA。预处理时间复杂度为O(NlogN)，查询为O(logN)。

实现步骤：

DFS预处理每个节点的深度和2^k级祖先
查询时先将两个节点调整到同一深度
然后一起向上跳，直到找到LCA

核心代码：

int lca(int x, int y) { if(dep[x] < dep[y]) swap(x,y); // 将x跳到与y同深度 for(int k=MAXLOG-1;k>=0;k--) if(dep[f[x][k]]>=dep[y]) x=f[x][k]; if(x==y) return x; // 一起向上跳 for(int k=MAXLOG-1;k>=0;k--) if(f[x][k]!=f[y][k]) x=f[x][k], y=f[y][k]; return f[x][0]; }