爱丽丝的人偶符法

题目描述

有 n 个人偶排成一棵树（n-1 条边），每个人偶 i 有：

• 初始状态 init[i]（0 或 1）
• 目标状态 goal[i]（0 或 1）

每次操作可以选择一个人偶，将其子树中与它深度同奇偶的所有节点翻转（0→1, 1→0）。注意：选中的节点自己也会翻转（深度差=0，偶数）。

请计算最少需要多少次操作，才能使所有人偶从初始状态变为目标状态。

数据范围： 1 ≤ n ≤ 10³

示例

输入：

5
1 2
2 3
4 5
3 4
0 0 0 0 0
1 1 1 1 1

输出： 2

说明： 所有节点初始都是 0，目标都是 1。需要 2 次操作。

解题思路

核心洞察： 操作的选择具有贪心性质。对于每个节点，其状态由两部分决定：

1. 祖先中同奇偶深度的操作次数（因为操作会影响子树中同奇偶深度的节点）
2. 自身是否需要翻转（init ≠ goal）

DFS 贪心：

从根开始 DFS，维护两个状态：

• evenOp：祖先中偶数深度节点被操作的次数 % 2
• oddOp：祖先中奇数深度节点被操作的次数 % 2

对于当前节点 u（深度 d）：

• 受影响的翻转 = (d % 2 === 0) ? evenOp : oddOp
• 当前是否需要翻转：need = init[u] !== goal[u]
• 如果 flip !== need（祖先操作的累积效果与期望不符），则必须在 u 这里操作一次，并更新对应的计数器

这种贪心策略的正确性在于：从根往下处理，每个节点只有一次机会被“从上方传递下来的操作”影响。如果当前效果不对，只能在当前节点操作来修正。

代码实现

function minOperations(n, edges, init, goal) {
    // 建邻接表
    const tree = Array.from({ length: n + 1 }, () => []);
    for (const [u, v] of edges) {
        tree[u].push(v);
        tree[v].push(u);
    }

    let ans = 0;

    function dfs(u, p, depth, evenOp, oddOp) {
        const need = (init[u] !== goal[u]) ? 1 : 0;
        const flip = (depth % 2 === 0) ? evenOp : oddOp;

        let curEvenOp = evenOp;
        let curOddOp = oddOp;

        if (flip !== need) {
            ans++;
            if (depth % 2 === 0) {
                curEvenOp = 1 - curEvenOp; // 翻转
            } else {
                curOddOp = 1 - curOddOp;
            }
        }

        for (const v of tree[u]) {
            if (v === p) continue;
            dfs(v, u, depth + 1, curEvenOp, curOddOp);
        }
    }

    dfs(1, 0, 0, 0, 0);
    return ans;
}

复杂度分析

• 时间复杂度： O(n)，每个节点访问一次。
• 空间复杂度： O(n)，存储邻接表和递归调用栈。

5
1 2
2 3
4 5
3 4
0 0 0 0 0
1 1 1 1 1

2