简介这是一份面向算法竞赛与信息学学习者的PDF笔记围绕基环树与笛卡尔树两类进阶树形结构展开。内容整理了两者的核心概念、构造思路与典型应用场景重点讲解笛卡尔树在直方图最大矩形、单调栈与虚树中的用法并针对POJ 2201、HDU 6305等题目给出解题方向基环树部分则覆盖相关专题小结、入门梳理与常见问题讨论。资源为单文件PDF大小仅93KB共6页便于按主题快速检索与打印阅读。目前已吸引500人学习适合正在备战信息学竞赛、ACM训练或复习数据结构的读者。借助这份提纲式资料无论是初学还是冲刺阶段都可以快速串联相关博客与经典例题建立从基础概念到具体题型的完整认知避免东拼西凑查资料节省大量筛选与理解时间。 如果你已经能熟练手撕树形DP、单调栈这类基础工具那“基环树”和“笛卡尔树”就是你进阶路上绕不开的两个名字。2021年9月6日那份标着(E)的笔记前半部分还在讲环套树的DP套路后半部分就跳到了笛卡尔树的单调栈建树当时学得挺过瘾但回头看也踩了不少坑。这篇文章就把那天整理的内容重新捋一遍把我自己调试代码时遇到的问题也一并写出来希望能给正在啃这两个结构的同学一点实在参考。基环树图论味道重核心思路是“先拆环再DP”笛卡尔树则是序列结构题里的利器核心是“用单调栈一次建树”。两者名字里都带“树”但解题套路完全不同。适合已经掌握基础树论、会写简单树形DP和单调栈、想进阶中级算法题的读者。1. 为什么这两个“树”值得放在一起啃1.1 先看清它们各自在解决什么问题基环树严格说不是树而是“比树多一条边”的连通图。树是 n 个点 n-1 条边基环树是 n 个点 n 条边多出来的那条边会在图里生成一个唯一的环。这类结构经常出现在“每个人只能选/依赖另一个人”的题目背景里比如社交网络中的关注关系、任务调度中的互斥选择本质就是一个环上挂着一堆普通树。笛卡尔树则完全不同它把数组序列映射成一棵二叉树同时满足“中序遍历是原序列”和“堆性质”。也就是说这棵树的形态完全由序列本身决定。它最大的价值在于很多区间最值问题、直方图矩形问题都可以在笛卡尔树上做文章把区间查询变成树上操作。这两个东西放在一起学不是因为它们长得像而是因为它们都考察同一个能力把一个看起来复杂的问题结构拆成“环/链/子树”这种能递推处理的部分。基环树拆的是图结构笛卡尔树拆的是序列结构拆完以后都靠DP或者树上统计收尾。1.2 从笔记(E)里我提取的学习顺序那天笔记的顺序是先基环树、后笛卡尔树我后来复盘觉得这个顺序挺科学。基环树需要你熟练“破环为链”的思维而笛卡尔树需要你熟练“单调栈维护右链”的思维两者都要求先掌握一个基础工具再叠加结构特性。我建议你也按这个顺序来先把无向基环树的找环和树形DP写熟再去碰笛卡尔树的建树和应用。不要跳着学因为基环树里的“环上枚举断边”这种操作能帮你建立处理环形依赖的直觉而笛卡尔树建树时的右链变换又很像基环树破环后的链式处理。两个结构互相印证手感会起来得很快。2. 基环树树形DP只是热身重头戏在环上2.1 基环树到底是什么先看定义。一个 n 个点、n 条边的弱连通无向图就是基环树。你可以理解为先画一棵树再在任意两个点之间加一条边于是形成一个环环上的每个点还可以向外挂着若干棵子树。如果图不连通每个连通分量都是基环树那就叫基环树森林。解题时通常要分别处理每个连通块再把答案汇总。题目背景往往隐含着“每个连通块独立”比如著名的“骑士”问题一共有 n 个骑士每个骑士有且仅有一个痛恨的人不能同时选择互相痛恨的两个骑士每个骑士有战斗力求最大战斗力总和。这个“每个骑士只有一个痛恨对象”的条件恰好会形成基环树森林。基环树的题目形态虽然多但处理框架非常固定第一步找环第二步把环上的每个点当成一棵子树的根对子树做树形DP第三步在环上做环形DP。这套路不知道在多少题里出现过熟练以后基本是流水线操作。2.2 找环的两条路线与实际取舍找环是基环树的第一步也是最容易出 bug 的一步。我自己用过两种主流方法各有适用场景。第一种是拓扑删叶法。从所有度为 1 的节点开始一层层剥离叶子节点类似拓扑排序。删除过程中不断更新相邻节点度数最后剩下的、度仍大于等于 2 的点就都在环上。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(); inCycle[u] 0; // 不在环上 for (int v : g[u]) { if (--deg[v] 1) q.push(v); } }这段代码跑完后inCycle[i] 1的点就是环上节点。优点是好写、不容易递归爆栈缺点是如果题目图里有重边导致“两个点两条平行边”这种特殊环靠度数判断可能会失效需要额外处理。第二种是DFS 时间戳找环。给每个节点记录访问时间戳用状态数组标记访问中、访问完。DFS 过程中如果遇到一个正在访问中的邻居说明找到了环。这种方法能直接输出环路径不用额外重建但递归深度大在 n 到十万级别时容易栈溢出。我一般会改成手写栈或直接用拓扑法。实际做题时我优先用拓扑删叶法因为它不依赖递归而且找环的代码能和后续树形DP分得很清。如果明确知道没有重边和自环这个方法就是最省心的。2.3 基环树DP的标准套路与代码骨架找完环以后套路就四步走先对每个环上节点做一次“挂载树”的树形DP再把环上节点按顺序拉直成链最后枚举断边做一次链上DP。以“骑士”这道题为例状态设计是dp[u][0/1]表示以 u 为根的子树中u 不选/选时能获得的最大战斗力。子树部分的转移很简单void dfs_dp(int u, int fa) { dp[u][0] 0; dp[u][1] val[u]; for (int v : g[u]) { if (v fa || inCycle[v]) continue; // 跳过环上节点 dfs_dp(v, u); dp[u][0] max(dp[v][0], dp[v][1]); dp[u][1] dp[v][0]; } }跑完这遍环上每个节点 i 都得到了两个初始值dp[i][0]和dp[i][1]。接下来把环断开问题变成在环上相邻节点不能同时选的情况下求最大值。做法是把环复制成两倍长度的链枚举第一个节点选或不选然后线性 DP。需要特别注意的是环上最后一段的相邻关系也要判断否则会漏掉边界状态。这套流程看着简单但我在初学阶段栽过两次跟头一次是忘记枚举断开边时“断点两侧也要考虑互斥约束”另一次是把环上节点当普通树节点直接记忆化搜索结果因为环的存在死循环。建议你写完后找小数据暴力对拍把环上节点、每条边的选择状态都打印出来核对。3. 笛卡尔树用单调栈一次把序列建成二叉树3.1 定义中序遍历加堆性质一棵由序列决定的树笛卡尔树的定义听起来有点“缝合”这是一棵二叉树每个节点对应原序列的一个位置节点权值就是序列值。这棵树要满足两个条件第一中序遍历得到的序列必须和原数组完全一致。也就是说如果按左子树、根、右子树的顺序遍历读出的值就是原序列从左到右的顺序。第二这棵树满足堆性质。以小根堆为例任意一个节点的权值都小于等于它子树里所有节点的权值。换句话讲根节点是整个区间的最小值左子树对应左半区间的最小值右子树对应右半区间的最小值递归下去。因为这两个性质笛卡尔树的形态是唯一的如果处理了相同值的顺序问题。你可以把它看成是“静态的 Treap”Treap 是靠随机优先级维护平衡而笛卡尔树的优先级就是序列值本身。这棵树特别适合用来做区间最值问题因为区间[l, r]的最小值节点恰好就是原序列区间对应到树上的 LCA。3.2 单调栈建树算法流程与小样例模拟笛卡尔树的建树方法有很多但竞赛里最常用的就是单调栈复杂度 O(n)。核心思路是从左到右扫数组维护一条从根一路向右延伸的“右链”栈。新节点来的时候把栈里所有值比它大的节点弹出最后一个被弹出的节点挂为它的左儿子如果栈里还有节点那这个新节点就挂为栈顶的右儿子然后新节点入栈。struct Node { int l, r, fa, val; } tr[N]; int stk[N], top 0; for (int i 1; i n; i) { int last 0; while (top tr[stk[top]].val tr[i].val) { last stk[top--]; } if (top) { tr[stk[top]].r i; tr[i].fa stk[top]; } if (last) { tr[i].l last; tr[last].fa i; } stk[top] i; }我拿一个具体序列走一遍。假设数组是[3, 1, 2, 4, 0]建小根笛卡尔树扫到 3栈空3 入栈。扫到 1栈顶 3 大于 1弹出 3last 3栈空把 3 挂为 1 的左儿子1 入栈。扫到 2栈顶 1 小于 2不弹出把 2 挂为 1 的右儿子2 入栈。扫到 4栈顶 2 小于 4不弹出把 4 挂为 2 的右儿子4 入栈。扫到 0依次弹出 4、2、1last 1栈空把 1 作为 0 的左儿子0 入栈。最后中序遍历核对0 的左子树是 11 的左子树是 3右子树是 22 的右子树是 4中序输出就是 3, 1, 2, 4, 0完美。这个过程最关键的一点是新节点永远暂时处于最右位置只有遇到更小值才会把前面一段右链“翻转”成自己的左子树。你如果理解了这一段建树代码就不会记混。3.3 经典应用最大矩形、区间最值、同构判断建好笛卡尔树后一系列问题都会变得很直观。比如“直方图最大矩形”每个柱子的高度是节点权值以小根笛卡尔树看任意节点 u 的子树在序列上对应一段连续区间这个区间内 u 的高度是最小值。所以以这个高度为矩形上界时最大宽度就是子树区间长度。答案就是所有节点的val[u] * (区间长度)取最大值。我常用递归统计子树大小一遍就出来。再比如“求所有区间的最小值之和”每个节点作为最小值能作为最小值的区间个数等于左子树大小 * 右子树大小相关的组合数。这个题在力扣上有原题用笛卡尔树做非常优雅不用单调栈维护四个边界数组。还有一类比较“冷门但有意思”的用法是用来判断两个序列的 RMQ 结构是否同构。因为笛卡尔树形态唯一两个序列的“区间最小值位置信息”一致当且仅当它们的笛卡尔树同构。这种题目在面试和竞赛里都有出现过。4. 实战中我踩过的坑附排查思路4.1 基环树排错记录坑一拓扑找环在重边/自环下失效。如果两个点之间存在两条平行边它们会形成一个度数为 2 的“环”但单纯靠度数删点不会把这两个点识别为环上节点。我后来在题目明确没有重边时才敢直接用拓扑法否则我会在加边时记录每条边的唯一性或者改用 DFS 时间戳找环。坑二环上 DP 忘记“破环为链”后的首尾约束。环形 DP 的本质是枚举第一个点选/不选两种状态。你如果只是简单复制数组while 循环里没有把n和n1的关系处理对答案多半会差一个边界的值。我的经验是复制数组时多申请一倍空间然后把最后一段的转移单独打印出来看。坑三把基环树当普通树递归导致死循环或爆栈。基环树上有环普通记忆化搜索在环上会无限递归。处理方式是在 DFS 入口判断inCycle[v]跳过环上邻居或者用状态数组标记访问中。4.2 笛卡尔树常见问题坑一弹出条件写成还是。如果序列里有相同值用会让后出现的相等值成为右子树节点用则会不断弹出相等值改变树的形态。实际做题时如果题目没有特殊要求我建议统一用保证同值元素的相对顺序稳定这样不容易被卡。坑二建树后没有做中序遍历校验。这个是我自己血的教训尤其是数组很大时左右儿子、父节点数组很容易有一两个赋值顺序错位。我每次建完树都会写一个递归中序遍历和原数组对一遍确认没问题再继续往下做。虽然多花几行代码但能避免 debug 两小时。坑三递归遍历笛卡尔树时爆栈。笛卡尔树在最坏情况下可以退化成一条链n 到十万级别时递归会爆。统计子树大小这类操作最好改成栈模拟后序遍历或者直接在原数组上利用左右子树区间维护信息绕过递归。5. 关于这两个结构我个人的一点实操经验基环树和笛卡尔树前者是图论的“环结构”思维后者是序列的“树结构”思维单独学都不难难的是在题目里识别出该用哪个。我自己有个习惯拿到题先问自己图的边数比点数多几条如果恰好是多一条边而且每个点只有一个特殊依赖那十有八九是基环树如果题目给的是一个数组并且反复强调“区间最小值/最大值”或者“矩形面积”我就会优先往笛卡尔树方向想。最后再分享一个建笛卡尔树的小技巧如果你和我一样总是记不住弹出后挂左右儿子的顺序就只记一句话——“弹出的最后一个节点变成新节点的左儿子”剩下的交给栈顶右儿子挂接处理。这句话救了我很多次希望也能帮到你。本文还有配套的精品资源点击获取