翻转树上最少边

给你一棵包含 n 个节点的无向树，节点编号从 0 到 n - 1。该树由长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

另外给你两个长度为 n 的二进制字符串 start 和 target。对于每个节点 x，start[x] 是其初始颜色，而 target[x] 是其目标颜色。

在一次操作中，你可以选择下标为 i 的一条边并翻转它的两个端点。也就是说，如果这条边是 [u, v]，那么节点 u 和 v 的颜色各自从 ‘0’ 变为 ‘1’，或者从 ‘1’ 变为 ‘0’。

返回一个边下标数组，执行这些边对应的操作可以将 start 转换为 target。在所有有效序列中找出长度最短的序列，以升序返回边下标。

如果无法将 start 转换为 target，则返回一个仅包含单个元素 -1 的数组。

思路

树的题目一般都可以用dfs来解决。

方法一：自底向上的 DFS

把问题看成： 每条边最多翻转一次，翻转后会影响这条边两端节点的颜色。对于每个节点，只关心它“最终是否需要被翻转奇数次”。

在树上做 DFS 后序遍历：

先处理子树

再决定是否通过“连接父亲的那条边”来修正当前节点

叶子节点的颜色如果与目标颜色不同，那么就一定要翻转和它相连接的两个节点，同时将边加入答案。移除原来的叶子节点，对新的叶子节点进行同样的操作。

点击展开/折叠代码

class Solution {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<vector<pair<int,int>>> g(n);
        for(int i=0;i<n-1;i++){
            int x=edges[i][0],y=edges[i][1];
            g[x].emplace_back(y,i);
            g[y].emplace_back(x,i);
        }
        vector<int> ans;
       std:: function <bool(int,int)> dfs=[&](int x,int fa)->bool{
            bool rev=start[x]!=target[x];
            for(auto& [y,i]:g[x]){
                if(y!=fa&&dfs(y,x)){
                    ans.push_back(i);
                    rev=!rev;
                }
            }
            return rev;
        };
        if(dfs(0,-1)){
            return {-1};
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

正确性说明

树结构保证：

    每个节点（除根）只有一条父边可以“补救”它

贪心是最优的：

    子节点问题必须在子树处理完后才能处理

    父边是唯一能影响子节点的外部操作

时间复杂度：O(n)，其中n为节点个数。空间复杂度：O(n)，其中n为节点个数。排序答案：O(n log n)

方法二：树上“异或差分”思想（等价但更直观）

核心思想

把每个节点需要的变化看成一个值：

need[x] = (start[x] != target[x]) ? 1 : 0;

翻转一条边 (u, v)：

相当于：need[u] ^= 1, need[v] ^= 1

目标：通过选一些边，使得所有 need[x] = 0

树上贪心策略

从叶子向根 DFS

如果某个子节点 y 的 need[y] == 1

那么必须翻转父边 (x, y)

否则 y 永远无法变成 0

翻转后：

need[y] = 0;
need[x] ^= 1;

算法流程

DFS 返回后，子节点要么是 0，要么已经通过父边解决

最终检查根节点：

need[root] == 0 → 可行

否则 → 无解

点击展开/折叠代码

class Solution {
public:
    vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
        vector<vector<pair<int,int>>> g(n);
        for(int i=0;i<n-1;i++){
            int u = edges[i][0], v = edges[i][1];
            g[u].push_back({v,i});
            g[v].push_back({u,i});
        }

        vector<int> need(n);
        for(int i=0;i<n;i++){
            need[i] = (start[i] != target[i]);
        }

        vector<int> ans;

        auto dfs = [&](this auto&& dfs, int x, int fa)->void {
            for(auto& [y, id] : g[x]){
                if(y == fa) continue;
                dfs(y, x);
                if(need[y]){
                    ans.push_back(id);
                    need[y] = 0;
                    need[x] ^= 1;
                }
            }
        };

        dfs(0, -1);
        if(need[0]) return {-1};

        sort(ans.begin(), ans.end());
        return ans;
    }
};

参考

灵茶山艾府

翻转树上最少边