最近在群里被问得最多的一道题就是美团的01树。3月21日这场笔试算法岗第四题、开发岗第三题都撞上了它。虽然题面不长但不少同学在考场上绕进了“从叶子往上翻”的误区最后只过了一半用例。这篇把这道题的完整思路和三种语言的写法都拆开讲一讲顺便把我在调试时踩过的坑也一起列出来。这道题本质是一道树上贪心代码量不大难点在于想清楚“翻转”这个操作到底是怎么传导的。一旦把状态定义对了代码二十分钟内能写完。我建议你先别急着看题解自己拿样例手推一遍再看下面的思路收获会大很多。1. 题目还原与第一眼直觉1.1 题目描述小美有一棵 n 个节点的树节点编号从 1 到 n根节点是 1。每个节点 u 上有一个权值 a[u]取值是 0 或 1。小美每次可以选择一个节点 v把以 v 为根的子树上所有节点的权值都翻转一次0 变成 11 变成 0。问最少需要操作多少次才能让整棵树上所有节点的权值都变成 0。输入格式第一行一个整数 n表示节点数量。第二行 n 个整数表示 a[1] 到 a[n]。接下来 n-1 行每行两个整数 u, v表示节点 u 和节点 v 之间有一条无向边。输出格式一个整数表示最少操作次数。样例输入一3 1 0 1 1 2 1 3样例输出一2样例输入二5 1 1 0 1 0 1 2 1 3 2 4 2 5样例输出二3这个数据范围一般 n 最大到 2e5 左右所以算法复杂度至少要是 O(n) 或 O(n log n)指数级做法肯定不行。1.2 样例手推为什么不是从叶子往上翻很多人第一反应是“从叶子开始遇到 1 就翻转”。但这个直觉在树上是错的因为翻转一个节点不会影响它的父亲却会影响它下面的所有子孙。如果你先把叶子处理干净再翻转某个祖先那叶子又会被翻回 1前面全白干了。拿样例一来说树是根 1两个孩子 2 和 3。权值分别是 1、0、1。最优做法是先翻转节点 2此时权值变成 1、1、1再翻转节点 1整棵树变成 0、0、0两次搞定。如果从叶子开始节点 2 已经是 0 不用管节点 3 是 1 要翻转一次最后节点 1 是 1 又要翻转一次看起来也是两次。但这个“看起来”不能推广稍复杂一点的树就会出问题比如样例二。样例二我直接给结论最优是 3 次。如果你尝试从叶子节点 4、5、3 开始逐个处理很可能会算出 4 次甚至更多。核心原因就是翻转顺序会影响后代状态所以必须换一个角度去理解这个操作。2. 从暴力到最优解题思路推导2.1 暴力的困境先想暴力。每个节点都可以选择“翻”或“不翻”一共 2^n 种方案。n 到 2e5 的时候这个数字大到没有意义所以必须找到某种结构化的决策方式。一个自然的想法是既然每个节点的操作都会影响子树内所有节点那能不能把“影响”拆成一个可以沿着树传递的状态这里的突破口是奇偶性。一个节点被翻转两次等于没翻转。所以每个节点实际只有两种状态操作一次或者不操作。多次操作没有意义可以把所有操作次数对 2 取模。于是问题变成了对每个节点 u决定一个变量 x[u] ∈ {0, 1}表示是否翻转节点 u使得最终所有节点的权值为 0并且让所有 x[u] 的和最小。2.2 关键观察翻转只影响后代不影响祖先题目操作是“翻转以 v 为根的子树”所以对于任意一个节点 u它的最终权值只受两类操作影响所有 u 的祖先包括 u 自己是否被翻转。和 u 平级或位于 u 上方的节点不会影响 u。重要推论节点 u 的最终权值不可能被它的后代节点改变。因为后代节点的子树不包含 u。这件事改变了整个思考方向。如果我们从根节点开始自上而下做决策那么处理到某个节点 u 的时候u 的所有祖先是否被翻转已经确定了。这个信息足以算出 u 当前显示的值是多少。如果当前值是 0我们就不需要翻转 u如果当前值是 1那必须在 u 这里翻一次因为现在不翻之后再也没有机会修正它了。这就是贪心。2.3 用一个 cur 变量传递状态定义 cur 表示从根到当前节点的路径上被翻转过的节点数量的奇偶性。换句话说cur 1 表示当前节点 u 已经被祖先们的操作翻转了奇数次所以 u 的“当前显示值”是 a[u] xor cur。算法流程从根节点 1 出发cur 0因为根节点没有祖先。对当前节点 u先看 a[u] xor cur 是不是 1。如果是 1说明 u 目前是 1必须翻转 u。操作次数加一同时 u 自己翻转了一次所以传给子节点的 cur 要变成 cur xor 1。如果是 0说明 u 目前已经是 0不需要翻转直接传给子节点原来的 cur。对每个子节点递归执行同样的过程。写成伪代码dfs(u, fa, cur): if a[u] ! cur: ans 1 cur cur ^ 1 for v in children[u]: dfs(v, u, cur)这里我用了a[u] ! cur来等价表达a[u] xor cur 1。因为 a[u] 和 cur 都只有 0 和 1 两种取值当它们不同的时候异或结果才是 1。2.4 正确性证明每一步都是强制决策很多人会担心为什么贪心是对的会不会存在一种情况现在翻转了 u导致后面某个子节点需要多翻一次整体反而不优这个担心是合理的但在这道题里不成立。原因是每个节点的状态是“自上而下”确定的子节点的操作永远影响不到父节点。具体证明可以用归纳法对于根节点它没有祖先所以它的最终值只取决于自己是否被翻转。如果 a[1] 1根节点最终一定是 1必须翻转如果 a[1] 0翻转根节点只会让整个树全部取反白白增加一次操作所以不翻。假设处理到节点 u 时cur 已经确定。cur 表示祖先对 u 的影响。如果 a[u] xor cur 1说明 u 当前值是 1。此时有两条路翻转 u或者不翻。如果选择不翻u 会一直是 1因为没有任何后代操作能改变 u最终必然不合法。所以这一步是强制的。如果选择翻转u 变成 0后代继承新的 cur整体走向唯一确定。因此每一个节点的决策都是被当前状态唯一确定的贪心得到的操作次数既是最小值也是唯一可行方案在“尽量少操作”意义上的最优解。这个证明放在面试里讲出来基本就是满分回答。3. 三种语言的落地实现3.1 Python 递归写法Python 写树题最省事但要注意递归深度。n 到 2e5 时如果树是一条链默认递归深度会直接爆掉。所以第一步要设置递归上限。import sys sys.setrecursionlimit(10 ** 6) def solve(): n int(sys.stdin.readline()) a [0] list(map(int, sys.stdin.readline().split())) g [[] for _ in range(n 1)] for _ in range(n - 1): u, v map(int, sys.stdin.readline().split()) g[u].append(v) g[v].append(u) ans 0 def dfs(u, fa, cur): nonlocal ans if a[u] ! cur: ans 1 cur ^ 1 for v in g[u]: if v ! fa: dfs(v, u, cur) dfs(1, 0, 0) print(ans) if __name__ __main__: solve()几个细节解释一下a [0] list(...)是为了让下标从 1 开始和节点编号对齐写起来不用老是减一。g是邻接表因为题目给的是无向边所以两个方向都要加。cur作为递归参数传递每次翻转后直接异或 1。nonlocal ans在 Python 3 里用于修改外层函数的局部变量不能漏。这个写法的时间复杂度 O(n)空间复杂度 O(n)在 Python 下跑 2e5 的数据没有问题大约零点几秒。3.2 Java 递归写法Java 的递归默认栈深度一般够用实测 2e5 的链式树在多数 OJ 上不会栈溢出但为了稳妥也可以在代码里手动建一个大数组模拟栈或者用new Thread(null, ..., 1 27).start()增大栈空间。下面先给常规递归版本。import java.util.*; public class Main { static int[] a; static ListInteger[] g; static int ans; public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); a new int[n 1]; g new ArrayList[n 1]; for (int i 1; i n; i) { a[i] sc.nextInt(); g[i] new ArrayList(); } for (int i 0; i n - 1; i) { int u sc.nextInt(); int v sc.nextInt(); g[u].add(v); g[v].add(u); } ans 0; dfs(1, 0, 0); System.out.println(ans); } static void dfs(int u, int fa, int cur) { if (a[u] ! cur) { ans; cur ^ 1; } for (int v : g[u]) { if (v ! fa) { dfs(v, u, cur); } } } }这里有个 Java 特有的小坑Scanner在数据量特别大的时候会有点慢。如果 n 达到 2e5输入行数接近 2e5用 Scanner 通常还能过但如果你担心超时可以换成BufferedReader加StringTokenizer。不过大多数春招笔试场景下Scanner 够用没必要过度优化。3.3 C 写法与性能优化C 对这种树的题可以说是主场栈深度一般不是问题速度也最快。这里用vectorint邻接表加上ios::sync_with_stdio(false)加速输入。#include bits/stdc.h using namespace std; const int MAXN 200005; vectorint g[MAXN]; int a[MAXN]; int ans; void dfs(int u, int fa, int cur) { if (a[u] ! cur) { ans; cur ^ 1; } for (int v : g[u]) { if (v fa) continue; dfs(v, u, cur); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; for (int i 1; i n; i) { cin a[i]; } for (int i 0; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0, 0); cout ans \n; return 0; }C 版本有几个可以优化的地方vectorint g[MAXN]是静态数组适合 n 固定的单组测试数据。如果是多组测试记得在每组开头把g[i].clear()清掉。cur是 int实际上只存 0 或 1。用bool也可以但 int 不用考虑类型转换写起来更顺手。如果担心系统栈深度不够可以把dfs改成手写栈迭代版本但大部分 OJ 2e5 深度没问题Linux 下默认栈一般有 8MB够用。3.4 复杂度与输入输出细节三种语言的算法复杂度完全一样时间复杂度每个节点访问一次O(n)。空间复杂度邻接表存储所有边O(n)递归栈深度最坏也是 O(n)。如果 n 的范围是 2e5这个复杂度是肯定能过的。真正的区分点往往在输入处理和递归边界这些细节上。4. 实战中踩过的坑与自测建议4.1 递归爆栈问题这是最容易翻车的地方。Python 默认递归深度只有 1000 左右链式树来 2e5 个节点不设置setrecursionlimit直接 RecursionError。Java 和 C 一般在 2e5 深度没问题但也不太绝对。如果你发现本地跑样例没问题、交上去却出现奇怪的运行时错误可以先怀疑递归深度。手写一个非递归栈版本其实也不难核心就是把dfs里的参数打包成三元组(u, fa, cur)存进栈里。stacktupleint, int, int st; st.push({1, 0, 0}); while (!st.empty()) { auto [u, fa, cur] st.top(); st.pop(); if (a[u] ! cur) { ans; cur ^ 1; } for (int v : g[u]) { if (v ! fa) st.push({v, u, cur}); } }这个迭代版本可以完全规避栈深度问题代价是代码稍微长了一点思路一模一样。面试时如果时间紧张还是优先写递归能跑通就行。4.2 常见错误忘记跳过父节点导致死循环树本身是无向图DFS 的时候必须判断v ! fa否则会反复横跳直接死循环或者栈溢出。我见过不少同学邻接表建图没错却忘了判断父节点结果样例都过不了还以为是递归cur传错了。这个错误很隐蔽因为小样例可能碰巧不会触发到数据量一大的树就崩了。写的时候有个小技巧把fa初始化为 0因为节点编号从 1 开始0 永远不会是合法父节点。这样根节点第一次进入递归时也不会被误判。4.3 构造边界数据自测考场上不能只靠题目给的样例。我一般会自己构造几组边界数据验证n 1树只有一个根节点。比如a[1] 1答案应该是 1a[1] 0答案应该是 0。整棵树全是 1。比如一条长度为 3 的链节点权值全是 1最优解是什么可以手推一下再跟代码跑出来的结果对比。整棵树全是 0。这种情况不管树长什么样答案都是 0。星型树根节点下面挂 n-1 个叶子。这种树操作起来很直观适合验证贪心方向。随机生成的树对比暴力枚举结果。n 在 15 以内时可以写一个枚举所有 2^n 方案的暴力程序随机生成几百组数据用贪心解和暴力解对拍。这是最稳妥的验证方式。对拍的时候注意暴力枚举的复杂度是 O(n * 2^n)n 别超过 15不然暴力本身就跑不动了。5. 这道题背后的扩展与总结5.1 变体如果操作改成翻转“根到节点路径”这个扩展我建议认真看一下因为美团常在同一次笔试里换着法子出类似的树题。假如操作变成“选择节点 v把根节点到 v 路径上的所有节点权值翻转”那影响方向就反过来了。翻转一个节点不会影响它的子节点但会影响它的所有祖先。这种情况下贪心顺序必须是从叶子往根走。思路是对于节点 u它的最终值只取决于子树内被操作的后代数量奇偶性。从叶子开始向上处理当处理到 u 时所有后代的决策已经完成u 当前值已经确定。如果 u 是 1就翻转一次 u因为翻转 u 会把从根到 u 的路径全部取反这是唯一能修正 u 的机会。核心代码就是从叶子向上做一次后序遍历判断条件仍然是a[u] ! cur只不过 cur 的含义变成了“子树内操作次数奇偶性”。5.2 面试时怎么把思路讲清楚面试官问这道题的时候最忌讳一上来就甩代码。我建议按这个顺序讲先说结论每个节点最多操作一次。再说影响方向翻转子树只影响后代所以必须自上而下决策。定义状态 cur传递祖先操作次数的奇偶性。给出判断条件当前节点显示值为 1 时必须翻转。最后补充一句这个贪心是强制的不存在更优解。这样讲下来面试官能很清楚看到你是在“思考”而不是在“背题”。代码反而是最后才写的东西。5.3 我个人的一些体会这道题本身不难但它很能考察一个人对“操作影响范围”的敏感度。很多人会把“翻转子树”当成普通的区间翻转想用线段树或者差分数组去维护反而把问题复杂化了。我自己的经验是遇到树上操作问题先画一棵小树把每个操作的影响范围画出来问自己三个问题——这个操作影响谁先做和后做有什么不同能不能用一个状态沿着树传递把这三点想清楚90% 的树上贪心题都能迎刃而解。最后再分享一个小技巧如果你在笔试时实在判断不出是从上往下还是从下往上就用“父节点会不会被子节点影响”来判断。会就从叶子开始不会就从根开始。这道题就是典型的“不会”所以从根开始做。记住这个小规律下次遇到类似题目能少走很多弯路。