![[蓝桥杯]真题剖析：砍树（从暴力DFS到树上差分+LCA的算法演进）](images/page-header-bg.jpg)
![[蓝桥杯]真题剖析：砍树（从暴力DFS到树上差分+LCA的算法演进）](http://pic.xiahunao.cn/yaotu/[蓝桥杯]真题剖析：砍树（从暴力DFS到树上差分+LCA的算法演进）)
1. 从暴力DFS到树上差分砍树问题的算法演进第一次看到蓝桥杯这道砍树题目时我和大多数选手一样第一反应就是用DFS暴力搜索。题目大意是给定一棵树和若干路径要求找到满足所有路径都经过的边中编号最大的那条。直接思路很直观对于每条路径用DFS标记经过的边最后统计被标记m次的边。我写的第一个版本和题目给出的暴力代码几乎一模一样。这个解法虽然直观但当树节点数N1e5路径数M1e5时时间复杂度直接飙到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; }; vectorEdge edge[N];这样在DFS时可以直接获取边的编号省去了map查询的开销。虽然这不能改变时间复杂度但在实际运行中能减少常数时间。3. 树上差分从O(MN)到O(MN)的飞跃3.1 差分数组的思想迁移差分是处理区间修改的高效技巧。在一维数组中要给区间[l,r]统一加1我们只需要在l位置1r1位置-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(MN)完全能够处理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 kMAXLOG-1;k0;k--) if(dep[f[x][k]]dep[y]) xf[x][k]; if(xy) return x; // 一起向上跳 for(int kMAXLOG-1;k0;k--) if(f[x][k]!f[y][k]) xf[x][k], yf[y][k]; return f[x][0]; }4.3 树链剖分求LCA另一种高效的LCA算法是树链剖分虽然预处理时间复杂度也是O(N)但实际运行效率通常比倍增法更快。题目给出的正解代码就是采用的这种方法。树链剖分通过两次DFS将树划分为重链查询LCA时沿着重链向上跳直到两个节点位于同一条链上。5. 完整解题思路与代码实现5.1 算法流程总结读入树结构建立邻接表预处理LCA需要的信息树链剖分或倍增处理每条路径找到u和v的LCA在u和v处1在LCA处-2后序遍历计算子树和找出满足w[i]m的边中编号最大的5.2 关键实现细节在实际编码中有几个容易出错的细节需要注意边的编号处理题目中边编号是1-based还是0-based差分标记时根节点的特殊处理最后统计答案时要检查边的两个端点完整代码可以参考题目给出的正解但建议自己实现一遍加深理解。我在第一次实现时就因为没处理好边的编号导致WA调试了很久才发现问题。6. 算法选择与性能对比6.1 暴力DFS vs 树上差分暴力DFS的优点是实现简单适合小规模数据。但当N和M超过1e4时就必须考虑更高效的算法。树上差分虽然实现复杂一些但能够将时间复杂度从O(MN)降到O(MN)是质的飞跃。6.2 不同LCA算法的比较在实际比赛中如果时间紧迫可以选择实现相对简单的倍增法。如果对性能要求极高树链剖分是更好的选择。还有Tarjan离线算法等其他选择但编码复杂度较高。7. 类似问题的扩展思考砍树问题的核心是统计被所有给定路径覆盖的边。类似的问题还有很多比如统计被至少k条路径覆盖的边找到被最多路径覆盖的边动态添加/删除路径实时查询这些变种问题都可以基于树上差分的思想来解决只是差分标记和统计的方式需要相应调整。掌握这类问题的解题思路对参加算法竞赛很有帮助。
