最近刷题进度到了第2747题碰上的是 P3621 [APIO2007] 风铃。说实话第一眼看到“交换左右子树”我差点想直接写一棵平衡树去模拟还好先冷静下来推了一下性质。这道题真正考的不是交换操作本身而是树上叶子深度统计加子树状态合并C 实现很短但“为什么这么判”才是最有价值的部分。这篇文章把题面拆解、核心算法、完整代码和提交时容易翻车的点全部过一遍适合刚刷完二叉树、想进阶树形 DFS 状态合并的选手。1. 题面拆解为什么“交换”是个幌子1.1 不变量是叶子深度先想一个最基本的问题对某个节点执行“交换左右子树”到底改变了什么答案很反直觉它什么深度信息都没改变。每个叶子到根的距离也就是深度完全取决于它从根往下走了多少层。你把一棵子树整体换到右边这棵子树里每个叶子的层数不会变只是它在整个风铃里的左右位置变了。所以题目给了一棵具体树之后所有叶子深度的集合就已经是定死的了。交换操作唯一能改变的是“哪些叶子出现在哪一侧”改变不了“叶子有多深”。这道题能被简化成纯 DFS核心就是看准了这个不变量。1.2 最大最小深度差是生死线既然叶子深度集合固定那第一步就是把所有叶子的最大深度和最小深度扫出来。记作 minD 和 maxD然后分三种情况情况结论maxD - minD 1直接无解输出 -1maxD minD所有叶子一样高已经满足输出 0maxD - minD 1只剩两种深度需要进一步判定和统计答案为什么差值大于 1 就完全没救因为无论你怎么交换最浅的叶子和最深的叶子永远存在两者深度差是常量不可能通过重新排列左右子树把它缩小。这就好比箱子里的商品只有两种规格时整理起来很轻松一旦规格超过两种光靠分类动作根本无法改变规格本身。只有当所有叶子深度只有两种且相差 1 时问题才真正有讨论空间。此时把所有深度为 minD 的叶子看作“浅色”深度为 maxD 的叶子看作“深色”整个问题就变成了一个纯粹的“两种颜色归位”问题。2. 判定与计数两种深度就是两种颜色2.1 混合状态是唯一需要担心的把叶子抽象成浅色和深色之后一棵子树的状态就可以分成三类纯浅子树里只有 minD 深度的叶子。纯深子树里只有 maxD 深度的叶子。混合子树里浅色、深色叶子都有。这里有一个关键结论如果某个节点的左右两棵子树都同时包含浅色和深色那么这棵子树无论怎么交换都不可能整理成合法形态整体无解。原因很直白。交换操作只会把左子树整体换到右边、右子树整体换到左边。如果左右两边本来就是“混合对混合”交换一次之后依然是“混合对混合”问题规模一点都不会变小。混合状态必须靠更下一层的递归来处理前提是至少有一侧是纯色这样纯色的一侧可以作为“稳定锚点”把另一侧的混合状态慢慢消化掉。一旦出现左右都混合这个节点就成了一个死结它本身永远达不到“一侧纯色、另一侧纯色”的状态上层再怎么换也只能移动这个死结的位置不能解开它。2.2 用两个 bit 表示子树状态因为只有两种深度状态可以用一个 int 的低两位表示比返回结构体或者 pair 更干净0空子树没有任何叶子贡献。1只有浅色叶子。2只有深色叶子。3深浅都有即混合状态。合并左右子树的时候直接按位或。为什么要用按位或你自己手推一遍就明白了左子树是 1浅色右子树是 2深色1 | 2 3当前节点混合。左子树是 2深色右子树也是 2深色2 | 2 2当前节点纯深。左子树是 3混合右子树是 1浅色3 | 1 3当前节点仍然是混合。左状态右状态合并结果含义111纯浅222纯深123混合213混合313混合333混合且左右都混合状态合并只要一行代码却把一棵子树的全局信息压缩得明明白白。这也是整道题实现层面最舒服的地方。2.3 什么时候答案加一当某个节点最终的合并状态为 3也就是当前子树确实混合时需要分情况看左右子树的状态左子树状态为 2右子树状态为 1说明左边整片全是深色右边整片全是浅色。为了让整理方向统一需要一次交换把左右对调变成左浅右深ans 加 1。左子树状态为 1右子树状态为 2已经满足左浅右深不需要在这个节点上操作。一边是纯色另一边是混合当前节点不用交换把混合的那一侧交给递归继续处理。因为混合侧的整理不受这个节点交换的影响。左右都是混合前面说过直接无解。这里“统一方向”是我个人实现时固定的规则浅色靠左、深色靠右。如果你习惯反过来也完全可以只是 leftState 2 rightState 1 这个计数条件要对应调整。本质上一个“左深右浅”的混合节点必须交换一次才能变成“左浅右深”这恰好就是最少交换次数。举一个非常直观的小例子。根节点 1 的左儿子 2 是内部节点它的两个儿子 4、5 都是深度为 2 的叶子属于深色根节点的右儿子 3 是深度为 1 的叶子属于浅色。此时 minD 1maxD 2。根节点左子树状态是 2右子树状态是 1合并后为 3触发计数条件ans 1。手动交换根节点左右子树之后风铃变成左侧浅色、右侧深色只花了一次交换。3. C 实现完整代码与关键细节3.1 建树与深度扫描输入给的是每个节点的左右孩子编号0 表示空。我用两个数组 L 和 R 存孩子BFS 从根节点 1 开始跑深度。叶子节点的判断条件就是左右孩子都为 0。BFS 的过程中顺手更新 minD 和 maxD。注意不要在主函数里先用循环跑所有节点更新深度除非你提前存好了父子关系。最稳妥的做法就是队列从根出发边跑边记录深度这样每个节点只访问一次。3.2 后序 DFS从叶子向上合并状态深度扫描完之后如果差值不是 1直接按对应结果输出。只有差值恰好为 1 时才进入 DFS。DFS 是标准的后序模式先处理左子树再处理右子树最后合并状态。叶子节点根据自身深度返回 1 或 2因为此时只有两种深度不存在第三种情况。内部节点把左右子树返回的状态做按位或然后判断无解条件和答案累加条件。这里有个容易忽略的点判断无解用的是“左右子树都是 3”而不是“当前节点是 3”。如果当前节点是 3但左边是 3、右边是 2这不是无解右边纯深可以作为稳定侧左边混合继续递归整理。真正无解是左右都不能独立消化。3.3 完整程序代码#include bits/stdc.h using namespace std; const int MAXN 100005; int n; int L[MAXN], R[MAXN]; int depthArr[MAXN]; int minD INT_MAX, maxD -1; int ans 0; bool possible true; void calcDepth() { queueint q; depthArr[1] 0; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); if (L[u]) { depthArr[L[u]] depthArr[u] 1; q.push(L[u]); } if (R[u]) { depthArr[R[u]] depthArr[u] 1; q.push(R[u]); } if (!L[u] !R[u]) { minD min(minD, depthArr[u]); maxD max(maxD, depthArr[u]); } } } int dfs(int u) { if (!L[u] !R[u]) { return (depthArr[u] minD) ? 1 : 2; } int leftState dfs(L[u]); int rightState dfs(R[u]); int state leftState | rightState; if (leftState 3 rightState 3) { possible false; } if (state 3 leftState 2 rightState 1) { ans; } return state; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin L[i] R[i]; } calcDepth(); if (maxD - minD 1) { cout -1 \n; return 0; } if (maxD minD) { cout 0 \n; return 0; } dfs(1); if (!possible) { cout -1 \n; } else { cout ans \n; } return 0; }代码量不大核心逻辑全部集中在两个函数里。主函数在 maxD - minD 1 和 maxD minD 时提前退出可以有效避免不需要的 DFS。4. 提交时容易翻车的地方4.1 递归爆栈100000 层怎么办这题节点数可以到 100000大多数递归写法在链状数据下会爆栈。洛谷很多题的递归题解能过是因为数据没把树退化到极限或者评测机栈空间比较大。但换一个严格的 OJ递归直接 RE 也是常有的事。想稳妥一点可以在本地用栈扩容比如 MSVC 环境下加#pragma comment(linker, /STACK:102400000,102400000)但这不是跨平台的通用解法。更推荐的做法是把后序 DFS 改成手写栈。核心思路是用一个 vis 数组区分“第一次访问”和“子节点处理完毕”vectorint state(n 1, 0); vectorint stk; vectorint vis(n 1, 0); stk.push_back(1); while (!stk.empty()) { int u stk.back(); if (!vis[u]) { vis[u] 1; if (L[u]) stk.push_back(L[u]); if (R[u]) stk.push_back(R[u]); } else { stk.pop_back(); int leftState L[u] ? state[L[u]] : 0; int rightState R[u] ? state[R[u]] : 0; state[u] leftState | rightState; if (leftState 3 rightState 3) possible false; if (state[u] 3 leftState 2 rightState 1) ans; } }第一次访问节点时只标记 vis 并压入左右孩子第二次弹栈时孩子状态已经全部算完这时候做合并和计数。逻辑和递归版本完全一致但没有爆栈风险。4.2 无解输出到底是 -1 还是 0这一点容易让人卡很久。P3621 在洛谷的题面要求无解时输出 -1而不是 0。我最早就是因为按照某些博客写的“输出 0”交上去 WA 了好几次。不同 OJ 对 APIO 原题的输出格式翻译可能略有差异提交前一定确认你做的 OJ 要求的到底是哪个。代码按照当前题面写 -1如果是自测平台再对照题目要求调整。4.3 所有叶子同深度时不要进 DFSmaxD minD 时直接输出 0不要继续跑 DFS。虽然按道理所有叶子状态相同DFS 也能跑出一个结果但很容易因为状态合并的细节算出一个非零 ans反而把正确结果覆盖。提前返回是最安全简洁的写法也避免了不必要的计算。4.4 问题排查速查表现象可能原因处理方式输出比预期小叶子同深度时没提前返回ans 被错误计算maxD minD 直接输出 0输出比预期大无解时 still 累加了 ans无解判定后再输出用 possible 变量兜底递归 RE树退化接近链状栈溢出改手写栈或用 pragma 扩容WA 在输出 0 / -1无解值没对齐当前 OJ 约定确认题面要求的无解输出值5. 复盘这道题给后面题目留了什么经验5.1 树上信息自底向上合并的代码模型这题的 DFS 本质是“后序遍历时从子树收集信息再合并给父节点”。这个模型在信奥里非常常见后面做树上 DP、子树统计、直径类问题全是同一套骨架先递归子树拿到返回值再在父节点做状态转移。不同之处只在返回值的含义和合并规则。P3621 返回的是一个两比特状态树上 DP 返回的可能是一个数组或一个结构体。先把后序框架写熟后面遇到复杂状态就不会慌。5.2 交换类操作先找不变量这题最值得记的思维套路是看到“交换子树”这类操作先停下来思考什么是交换改变不了的。这题的不变量是叶子深度集合一旦意识到这一点很多无效的模拟思路立刻被砍掉。很多竞赛题都是这样操作描述越花哨背后不变量越简单。写代码之前先花十分钟找不变量远比直接上手模拟划算。5.3 状态压缩什么时候适用这道题能用两个 bit 压缩状态归根结底是因为只有两种深度。如果改成三种深度按位或就不再够用必须改成计数或更完整的结构。所以位运算状态不是万能的但它背后“用少量信息充分刻画子树性质”的思路可以沿用。以后遇到“只有两种颜色 / 两种类型”的树上整理题可以先想想能不能用类似的状态压缩。我做这道题时第一次 WA 是把无解输出成了 0第二次 TLE 是老老实实去模拟了交换。第三次重新读题解才意识到树上交换类题目几乎都有一个通用套路先找不变量再对子树状态做自底向上的合并。现在遇到这类题我会习惯性先问自己一句这个操作到底改变了什么没想清楚这个问题之前不急着写递归。