基环树与笛卡尔树详解：从找环断边到单调栈建树的竞赛指南

简介这是一份算法学习资料PDF面向备战算法竞赛或正在学习数据结构的读者核心围绕基环树与笛卡尔树展开并附带格雷码的编码知识点。作者结合自身刷题与阅读经验将散落在多篇博客中的关键内容浓缩在6页内以索引式笔记呈现既讲清笛卡尔树与单调栈、直方图最大矩形、POJ 2201、HDU 6305等经典问题的联系也汇总了算法模板与题解链接基环树部分从基础概念、环套树延伸到应用小结均有对应文章可跟随学习能帮助读者从零搭建框架避免在概念上绕路。格雷码部分则梳理了生成、解码、与二进制转换等要点可与数字逻辑、进制转换内容衔接方便横向拓展。资源为单个PDF文件体积仅93KB已有500人学习适合希望用较短时间概览多个相关知识点再通过文中链接深入研读的读者。 翻出这份《基环树 笛卡尔树--2021.09.06(E).pdf》的时候我正在整理第八轮省选模拟的讲义。当时印这份材料发给集训队主要就是为了解决一个长期悬而未决的问题很多树形DP题一旦把树换成基环树学生就开始瞎枚举断边一碰到区间最值贡献统计又绕不回单调栈。基环树和笛卡尔树这两块表面上一个研究“破坏后成树”的环结构一个研究“序列压成树”的排序结构但它们嵌套在题目里的频率高得吓人。这篇博文就直接把这份PDF里最核心的推导、代码框架和我在实际调试中踩过的坑铺开来讲适合正在备赛的中高级选手也适合想补全树论知识体系的读者。1. 整体思路为什么这两棵树要放在同一个PDF里讲1.1 两者的共同基因把“不是树”变成“树”先从直觉上说。基环树本质是树加上一条多余的边形成一个环笛卡尔树则是把一个数组按某种规则组织成一棵二叉树。前者让你面对的是一个“比树多一环”的结构后者让你面对的是一个“本来没结构”的序列。共同点在于处理它们都需要一套绕开常规DFS直接遍历的转换控制力。我当时在教案里写了一句很关键的话基环树的解题起点是先把环找出来笛卡尔树的解题起点是先把堆性质写清楚。这两步完成后剩下的遍历、状态转移、区间查询套路都很成熟。PDF里反复强调的也就是这两个“起点”。1.2 看这份讲义之前需要哪些前置知识树的基本遍历、树形DP套路尤其是换根DP单调栈的原理和应用LCA的倍增或树剖求法基础图论出度、入度、环的判定。如果你对这些概念还不够熟悉建议先把经典树题刷掉三十道再来看这份PDF否则第2章的找环代码和第3章的笛卡尔树线性建树都会显得像魔术。我个人觉得这两个结构放在一起还有一个隐藏好处你可以同时对比体会“环根树”与“堆序二叉树”在状态设计上的不同气质这对于做Ynoi模拟赛那种混合题特别有用。2. 基环树从“环树”的结构特点到断环处理2.1 结构分类外向基环树、内向基环树和无向基环树基环树本质上就是一棵树加上一条边之后形成的连通图简称“一个环上挂了一堆树”。根据边的方向性常见两种内向基环树每个点出度为1沿出边一直走必定走进环外向基环树每个点入度为1从环上节点出发指向若干子树无向基环树不区分方向通常用DFS判环或者在图上做拓扑删叶。无向版本在竞赛中最常见比如“求基环树直径”“基环树上两点距离”等题目。而有向版本常见于“每个点有一个出边”的模拟问题。理解分类的意义在于你会明白找环之后环上的每个点都可能挂一棵或多棵子树。2.2 找环的标准做法拓扑排序删叶子找环不推荐裸DFS原因很实际无向图的DFS判环要处理父亲边和返祖边的区分很容易写错有向图里还要额外判断环上的方向性。PDF里给出的方案是拓扑排序我个人用下来最稳。请看核心模板// 找出无向基环树中的所有环上节点 queueint q; for (int i 1; i n; i) if (deg[i] 1) q.push(i); while (!q.empty()) { int u q.front(); q.pop(); on_cycle[u] false; for (int v : G[u]) { if (--deg[v] 1) q.push(v); } }这段代码做完之后仍然保持on_cycle为 true 的点就都在环上。为什么采用拓扑删叶因为每次从叶子向内剥离最后剩下的就是核心环节点这个过程的时间复杂度是 O(n)比多次DFS搜环要稳定得多尤其适合环特别大比如 n1e6的情况。2.3 断环法枚举删除环上的哪条边基环树DP最常用的处理套路先找环然后枚举删除环上的某条边把基环树退化成普通树。例如求基环树直径时我们通常枚举删除环边 (u, v)再在退化的树上跑两次DFS求直径。这个做法的理论依据是任何一条合法的路径要么完全落在一棵子树中要么跨过环的一部分要么跨过被删除的那条边。由于我们枚举每一条环边所以一定能覆盖最优路径。复杂度是 O(环长 * n)对于环长是 O(n) 的题目来说总的复杂度是 O(n^2)这在 n 比较大的时候不够。但配合单调队列优化环上跨树路径合并后可以做到 O(n)。模板思路如下for (int i 0; i cir.size(); i) { int u cir[i], v cir[(i 1) % cir.size()]; // 删除边 u-v对每个环点跑一遍树形DP取直径 ans max(ans, solve_without_edge(u, v)); }2.4 基环树DP的经典处理环上合并子树答案单纯断环是最低配的做法。高阶选手一般会用“断成链后做线性DP”或“环上倍增”来优化。比如基环树求最长路每个环点先求出它挂载的子树最大深度dep[i]此时候选答案为跨环路径dep[i] dep[j] dist(i, j)。把环复制成两倍长度的链后dist(i, j)就可以用前缀距离直接算于是问题转化为滑动窗口求最大值// 把环复制成两倍长度利用单调队列优化 dequeint dq; for (int i 1; i 2 * m; i) { while (!dq.empty() i - dq.front() m) dq.pop_front(); if (!dq.empty()) { ans max(ans, dep[i] dep[dq.front()] (sum[i] - sum[dq.front()])); } while (!dq.empty() dep[dq.back()] - sum[dq.back()] dep[i] - sum[i]) dq.pop_back(); dq.push_back(i); }这里每一位变量的含义要清楚sum[i]是环上前缀距离dep[i]是当前环点挂载树的最大深度。2.5 实操心得找环后先打印环别上来就断我给所有学生的第一条建议是找完环先写一段打印环上节点编号的代码肉眼确认环找对了再开始DP。因为一旦环找错了后面所有on_cycle判断和断边枚举全部白搭。另一个常见的坑是自环或重边无向基环树如果出现重边拓扑排序删除叶子的时候两个点之间的度不会自然降到1需要额外判重边有向图出现自环时拓扑排序根本不会删它而在断边枚举时很容易漏掉。3. 笛卡尔树一个序列的堆序重构3.1 定义和唯一性中序遍历定序列堆序定父子关系笛卡尔树的定义看似简单一棵二叉树中序遍历是原数组顺序同时满足堆性质通常是小根堆也可以是大根堆。即对于任意节点其键值小于左右子树中所有节点的键值。但很多人没认真想过这样的树是唯一存在的。原因在于给定中序遍历顺序后最小的元素必须是根然后左右区间递归建根所以结构唯一确定。比如数组[3, 2, 1, 6, 4, 5]1是全局最小值它必然是整棵树的根左边区间[3, 2]以2为根右边区间[6, 4, 5]以4为根。这种递归划分性质使得笛卡尔树天然适合处理区间最值和分治类问题。3.2 单调栈线性建树原理直接按照上述递归划分建树是 O(n log n) 或 O(n^2)取决于你怎么找最小值。但利用栈的单调性我们可以在 O(n) 时间内完成构造。核心思想维护一条从根一直走右儿子的链右链栈中元素对应这条链上的节点且键值单调递增在小根堆约定下越往栈底越小。当新元素 x 到来时弹掉所有比 x 大的栈顶元素最后弹出的那个节点就会成为 x 的左儿子而 x 会成为新栈顶的右儿子。转换成代码就是for (int i 1; i n; i) { int last 0; while (!st.empty() a[st.top()] a[i]) { last st.top(); st.pop(); } if (!st.empty()) rc[st.top()] i; if (last) lc[i] last; st.push(i); }为什么是对的关键在“栈弹到不能弹为止”。每次操作后栈中元素仍然保持值递增且位置递增任何被弹出栈的元素都意味着它在原序列中已经找到了“右边第一个比它小的位置”它自然成为当前新节点的左子树。这个算法背后的直觉就是单调栈找左右第一个更小值只是我们把寻找结果物化成了树的父子关系。3.3 笛卡尔树在RMQ中的应用区间最值等于LCA笛卡尔树一个优雅的结论是原数组区间[l, r]的最小值等于节点l和节点r在笛卡尔树上的 LCA 节点的值小根堆情形。原因不复杂LCA 是同时位于 l 和 r 路径上方、值最小的节点且它的位置一定落在[l, r]区间内部否则会破坏中序遍历的顺序。这个性质的实际价值在于你可以把 RMQ 从“ST表预处理”换一种实现路径建笛卡尔树 LCA查询。在线查询 O(log n)虽然不比稀疏表 O(1)但它可以和树论的其他问题合并使用比如某些修改序列值的题目里笛卡尔树的形态变化远比ST表好维护。3.4 直方图最大矩形笛卡尔树的经典应用场景这是笛卡尔树最直观的入门应用题。给定一个直方图每个柱子的高度 h[i]求能画出的最大矩形面积。这个问题可以用单调栈做但用笛卡尔树做更好理解建一棵小根堆笛卡尔树以每个节点为高的矩形宽度就是它的子树在中序遍历中所覆盖的区间长度。于是最大矩形面积等于所有节点的高度乘以子树大小取最大值。void dfs(int u) { if (!u) return; sz[u] 1; dfs(lc[u]); dfs(rc[u]); sz[u] sz[lc[u]] sz[rc[u]]; ans max(ans, a[u] * sz[u]); }这里sz[u]在数字上等于以 u 为中序根节点的区间长度。为什么中序遍历区间长度能直接等于子树大小因为笛卡尔树的中序遍历就是原数组顺序任意节点的左子树全是它左侧比它晚“成为根”的连续区间右子树同理两者合并恰好覆盖完整区间。3.5 单调栈与笛卡尔树的联系严格来说笛卡尔树的建树过程离不开单调栈但反过来单调栈的许多问题也可以借助笛卡尔树来加深理解。比如“求每个位置左边第一个比它小的位置”——这就是笛卡尔树中每个节点的左子树最左节点在其左链上跳到的位置或者“所有区间最小值之和”这类计数问题求每个节点作为最小值的区间数量直接等于左子树大小 * 右子树大小。我一般建议学生会了单调栈就不必强制换成笛卡尔树写题但如果你已经掌握了笛卡尔树很多原本要费口舌证明的计数公式画一棵树就一目了然。4. 两种结构结合出的进阶题型4.1 结构上的相通之处环和堆序都是“约束转树”如果说基环树的难点在“找出那个多余的环”笛卡尔树的难点在“把序列的偏序关系转换为堆序”那么当两个结构出现在同一道题里时通常思路是“分治处理”外层用笛卡尔树做区间划分内层用基环树处理环上转移。比如某些关于“环上的区间最值”的题目先把环断开复制成链再用笛卡尔树维护链上区间最值。4.2 典型混合形态基环树上计区间最小值贡献假设题目要求给一棵基环树每个节点有权值求所有简单路径的最小值之和。暴力枚举所有路径是 O(n^2)行不通。一个可复用的思路是——借助笛卡尔树把“最小值贡献”这种全局问题转化为子树大小乘积的统计问题。先解决树部分对每个节点以它为最小值时能覆盖的路径数量等于左右侧可选端点数的乘积。再将环加入用断环成链 单调队列处理跨环路径。这时不需要真的把整棵基环树转换成笛卡尔树只要在环上套用区间统计即可。这种“树部分笛卡尔树统计 环部分断环合并”的组合套路我在多场模拟赛中都遇到过。4.3 踩坑提醒别在环上强行建笛卡尔树有一类题看起来是“在环上求区间最小值”有人会直接把环复制两倍然后建笛卡尔树。必须提醒复制后的长度为 2n但笛卡尔树中某些节点的子树可能包含长度超过 n 的区间这样统计会重复计数。正确做法是限制每个统计区间的长度不超过 n或者对环单独做单调栈而不是建笛卡尔树。5. 常见错误与调试技巧实录5.1 基环树找环最易错的三个点拓扑删除时机入队条件是deg[v] 1不是 1。重复入队会导致环上节点被误删。重边下的度处理邻接表存边时重边会让拓扑队列无法正确剥离链一般用set或map去重后再跑拓扑。有向图基环树入度判断出度为1的图拓扑删叶时按出度删除千万别直接照搬无向版的入度代码。5.2 笛卡尔树建树中常见的树形错乱建笛卡尔树最常见的错误是最后根的确定整棵树的根不是st[0]而是单调栈操作结束后栈底的元素。因为栈底保留的是全局最小值小根堆情形。另一个容易错的是左右儿子覆盖的问题尤其当last和栈顶右儿子同时存在时要检查是否出现了“一个节点同时有两个父亲”的情况。严谨的建树完毕之后建议从根开始跑一次中序遍历验证输出结果是否等于原数组。5.3 调试辅助用随机数据对拍和可视化输出无论基环树还是笛卡尔树我几乎都会用随机数据对拍。生成随机排列作为序列分别用按定义递归法和单调栈法建树再对比中序遍历序列是否一致。基环树部分则生成随机无向图用拓扑法找一个环再用DFS暴力判环对比。这类对拍脚本写熟之后基本20分钟内能保证正确性。可视化输出也很重要。把树邻接关系打印成括号表达式或者用Graphviz导出肉眼确认父子关系是否符合预期很多逻辑错误一下就暴露了。尾段一点个人的实践体会这套PDF的标题日期是2021.09.06但里面的方法直到现在我做题、出题都还在用。基环树的“找环—断边—合并”三步走和笛卡尔树的“单调栈—中序遍历—子树区间”三步走本质上都是“用已知的树形工具去压减未知结构的复杂度”。如果你看完这篇觉得代码都能默写建议立刻拿两道综合题练手比如“BZOJ 1791 岛屿”或者“Codeforces 1749E”把找环和笛卡尔树统计放在同一份代码里过一遍。踩过合并环上答案和区间值统计的坑之后你才算真正吃透了这份讲义。本文还有配套的精品资源点击获取