企业官网建设流程全解析

简介：这是一份面向算法竞赛与信息学学习者的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 的点，就都在环上。

queue<int> 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，弹出 3，last = 3；栈空；把 3 挂为 1 的左儿子；1 入栈。
• 扫到 2：栈顶 1 小于 2，不弹出；把 2 挂为 1 的右儿子；2 入栈。
• 扫到 4：栈顶 2 小于 4，不弹出；把 4 挂为 2 的右儿子；4 入栈。
• 扫到 0：依次弹出 4、2、1，last = 1；栈空；把 1 作为 0 的左儿子；0 入栈。

最后中序遍历核对：0 的左子树是 1，1 的左子树是 3，右子树是 2，2 的右子树是 4，中序输出就是 3, 1, 2, 4, 0，完美。这个过程最关键的一点是：新节点永远暂时处于最右位置，只有遇到更小值才会把前面一段右链“翻转”成自己的左子树。你如果理解了这一段，建树代码就不会记混。

3.3 经典应用：最大矩形、区间最值、同构判断

建好笛卡尔树后，一系列问题都会变得很直观。

比如“直方图最大矩形”：每个柱子的高度是节点权值，以小根笛卡尔树看，任意节点 u 的子树在序列上对应一段连续区间，这个区间内 u 的高度是最小值。所以以这个高度为矩形上界时，最大宽度就是子树区间长度。答案就是所有节点的val[u] * (区间长度)取最大值。我常用递归统计子树大小，一遍就出来。

再比如“求所有区间的最小值之和”：每个节点作为最小值，能作为最小值的区间个数等于左子树大小 * 右子树大小相关的组合数。这个题在力扣上有原题，用笛卡尔树做非常优雅，不用单调栈维护四个边界数组。

还有一类比较“冷门但有意思”的用法是用来判断两个序列的 RMQ 结构是否同构。因为笛卡尔树形态唯一，两个序列的“区间最小值位置信息”一致，当且仅当它们的笛卡尔树同构。这种题目在面试和竞赛里都有出现过。

4. 实战中我踩过的坑，附排查思路

4.1 基环树排错记录

坑一：拓扑找环在重边/自环下失效。如果两个点之间存在两条平行边，它们会形成一个度数为 2 的“环”，但单纯靠度数删点不会把这两个点识别为环上节点。我后来在题目明确没有重边时才敢直接用拓扑法；否则我会在加边时记录每条边的唯一性，或者改用 DFS 时间戳找环。

坑二：环上 DP 忘记“破环为链”后的首尾约束。环形 DP 的本质是枚举第一个点选/不选两种状态。你如果只是简单复制数组，while 循环里没有把n和n+1的关系处理对，答案多半会差一个边界的值。我的经验是：复制数组时多申请一倍空间，然后把最后一段的转移单独打印出来看。

坑三：把基环树当普通树递归，导致死循环或爆栈。基环树上有环，普通记忆化搜索在环上会无限递归。处理方式是在 DFS 入口判断inCycle[v]跳过环上邻居，或者用状态数组标记访问中。

4.2 笛卡尔树常见问题

坑一：弹出条件写成<还是<=。如果序列里有相同值，用<会让后出现的相等值成为右子树节点，用<=则会不断弹出相等值，改变树的形态。实际做题时，如果题目没有特殊要求，我建议统一用<，保证同值元素的相对顺序稳定，这样不容易被卡。

坑二：建树后没有做中序遍历校验。这个是我自己血的教训，尤其是数组很大时，左右儿子、父节点数组很容易有一两个赋值顺序错位。我每次建完树都会写一个递归中序遍历，和原数组对一遍，确认没问题再继续往下做。虽然多花几行代码，但能避免 debug 两小时。

坑三：递归遍历笛卡尔树时爆栈。笛卡尔树在最坏情况下可以退化成一条链，n 到十万级别时递归会爆。统计子树大小这类操作最好改成栈模拟后序遍历，或者直接在原数组上利用左右子树区间维护信息，绕过递归。

5. 关于这两个结构，我个人的一点实操经验

基环树和笛卡尔树，前者是图论的“环结构”思维，后者是序列的“树结构”思维，单独学都不难，难的是在题目里识别出该用哪个。

我自己有个习惯：拿到题先问自己，图的边数比点数多几条？如果恰好是多一条边，而且每个点只有一个特殊依赖，那十有八九是基环树；如果题目给的是一个数组，并且反复强调“区间最小值/最大值”或者“矩形面积”，我就会优先往笛卡尔树方向想。

最后再分享一个建笛卡尔树的小技巧：如果你和我一样总是记不住弹出后挂左右儿子的顺序，就只记一句话——“弹出的最后一个节点，变成新节点的左儿子”，剩下的交给栈顶右儿子挂接处理。这句话救了我很多次，希望也能帮到你。

本文还有配套的精品资源，点击获取