企业官网建设流程全解析

简介：这是一份算法学习资料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里给出的方案是拓扑排序，我个人用下来最稳。请看核心模板：

// 找出无向基环树中的所有环上节点 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(); on_cycle[u] = false; for (int v : G[u]) { if (--deg[v] == 1) q.push(v); } }

这段代码做完之后，仍然保持on_cycle为 true 的点，就都在环上。为什么采用拓扑删叶？因为每次从叶子向内剥离，最后剩下的就是核心环节点；这个过程的时间复杂度是 O(n)，比多次DFS搜环要稳定得多，尤其适合环特别大（比如 n=1e6）的情况。

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)就可以用前缀距离直接算，于是问题转化为滑动窗口求最大值：

// 把环复制成两倍长度，利用单调队列优化 deque<int> 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”，把找环和笛卡尔树统计放在同一份代码里过一遍。踩过合并环上答案和区间值统计的坑之后，你才算真正吃透了这份讲义。

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