2026-05-22：翻转树上最少边。用go语言，给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1。树用数组 edges 表示：共有 n-1 条边，edges[i]=[ai, bi] 表示 i 号边连接节点 ai 和 bi。再给你两个长度为 n 的二进制字符串 start 和 target，其中 start[x] 是节点 x 的初始颜色，target[x] 是节点 x 的目标颜色。

你可以进行若干次操作。每次操作你会选择一条边的下标 i，并把这条边两端点的颜色同时翻转：如果两端点原来是 0/1，那么翻转后就变成相反的颜色。也就是说，选择边 [u, v] 后，节点 u 与节点 v 的颜色都会从 0 变 1 或从 1 变 0。

你的任务是找出一组边下标序列，使得按顺序对这些边执行翻转操作后，最终 start 能变成 target。要求在所有可行的边序列中，找出“操作次数最少”的序列；如果有多种最短方案，则把对应的边下标按升序返回。若无论如何都无法把 start 变成 target，则返回 [-1]。

2 <= n == start.length == target.length <= 100000。

edges.length == n - 1。

edges[i] = [ai, bi]。

0 <= ai, bi < n。

start[i] 是 ‘0’ 或 ‘1’。

target[i] 是 ‘0’ 或 ‘1’。

输入数据保证 edges 构成一棵有效的树。

输入： n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]], start = “0011000”, target = “0010001”。

输出： [1,2,5]。

解释：

翻转下标为 1 的边，改变节点 1 和 2 的颜色。

翻转下标为 2 的边，改变节点 2 和 3 的颜色。

翻转下标为 5 的边，改变节点 1 和 6 的颜色。

执行这些操作后，结果字符串变为 “0010001”，与目标匹配。

题目来自力扣3812。

解题过程

先明确核心规则

1. 树是无向的，n 个节点，n-1 条边，边有固定下标；
2. 每次翻转一条边，会同时翻转这条边两个端点的颜色（0↔1）；
3. 目标：用最少次数的翻转，让 start 颜色变成 target 颜色；
4. 最少方案下，边下标按升序返回；无解返回 [-1]。

第一步：构建树的邻接表（存储结构）

把无向树转换成便于遍历的存储结构：

• 给每个节点记录它相邻的节点，同时记录这条相邻边的下标；
• 因为是无向边，每条边会在两个端点的邻接列表里各存一份；
• 作用：后续可以从根节点出发，沿着邻接关系遍历整棵树，且能精准找到每条边的下标。

第二步：确定遍历方式（深度优先搜索 DFS）

选择根节点（固定为 0 号节点），用后序遍历的方式遍历整棵树：

1. 从根节点 0 开始，递归访问它的所有子节点；
2. 遍历顺序：先处理所有子节点 → 再回到当前节点（自底向上处理）；
3. 遍历过程中，会区分父节点和子节点，避免回头遍历，保证树的遍历无环。

第三步：核心判断逻辑（当前节点是否需要翻转）

遍历到每个节点 x 时，做两个关键判断：

1. 初始状态：对比当前节点 x 的 start 颜色和 target 颜色
   • 如果颜色不一致：说明当前节点需要翻转；
   • 如果颜色一致：说明当前节点暂时不需要翻转。
2. 子节点影响：递归处理完所有子节点后
   • 如果子节点触发了边翻转，会间接改变当前节点的颜色（因为边连接父子节点，翻边会同时改两端）；
   • 子节点的翻边操作，会反转当前节点的需求（需要→不需要，不需要→需要）。

第四步：标记需要翻转的边

遍历过程中，一旦确定父子节点之间的边需要翻转：

1. 直接标记这条边的下标为「需要翻转」；
2. 翻转这条边会同时改变父节点和子节点的颜色，刚好修正子节点的颜色偏差；
3. 所有标记操作都在遍历中完成，只记录需要翻转的边，不重复操作（保证最少次数）。

第五步：最终合法性校验

遍历完整棵树后，回到根节点（0号节点）：

1. 根节点没有父节点，无法通过翻边单独修正它的颜色；
2. 如果最终根节点的颜色依然和目标不一致：
   • 说明无解，直接返回 [-1]；
3. 如果根节点颜色一致：
   • 说明所有标记的边就是最少操作方案。

第六步：整理结果（升序输出）

1. 遍历所有边的标记结果；
2. 把所有标记为需要翻转的边下标，按升序收集起来；
3. 返回这个有序列表，就是最终答案。

针对示例输入的完整执行过程（对应你的测试用例）

输入：
n=7，边：[[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]
start：0011000，target：0010001

1. 构建邻接表，记录每个节点的邻居和对应边下标；
2. 从根节点0开始DFS遍历，顺序：0→1→2→3→4、3→5、1→6；
3. 自底向上检查每个节点颜色：
   • 节点4、5颜色匹配，无需翻边；
   • 节点3颜色不匹配，触发翻转边2（连接2-3）；
   • 节点2被间接翻转后颜色不匹配，触发翻转边1（连接1-2）；
   • 节点6颜色不匹配，触发翻转边5（连接1-6）；
4. 所有子节点处理完毕，根节点0颜色匹配目标，校验通过；
5. 收集翻转的边下标：1、2、5，升序输出 [1,2,5]。

时间复杂度 & 额外空间复杂度

1. 总时间复杂度

O(n)

• 树有 n 个节点、n-1 条边；
• 邻接表构建：遍历所有边，O(n)；
• DFS 遍历：每个节点仅访问一次，每条边仅遍历两次（无向边），总操作数 O(n)；
• 结果收集：遍历所有边，O(n)；
• 整体线性时间，与节点数成正比。

2. 总额外空间复杂度

O(n)

• 邻接表存储：存储 n 个节点和 n-1 条边，空间 O(n)；
• 翻转标记数组：长度 n-1，空间 O(n)；
• DFS 递归栈：树的深度最坏为 O(n)（链状树）；
• 结果数组：最坏存储所有 n-1 条边，O(n)；
• 所有额外空间总和与节点数成正比，为线性空间。

总结

1. 解题核心：自底向上DFS遍历，通过子节点的翻边操作修正父节点颜色，保证最少操作次数；
2. 无解判断：根节点最终颜色无法匹配目标；
3. 效率：时间和空间均为线性复杂度 O(n)，完全适配题目 n≤10⁵ 的大数据量要求。

Go完整代码如下：

package main

import (
	"fmt"
)

func minimumFlips(n int, edges [][]int, start, target string) (ans []int) {
	type edge struct{ to, i int }
	g := make([][]edge, n)
	for i, e := range edges {
		x, y := e[0], e[1]
		g[x] = append(g[x], edge{y, i})
		g[y] = append(g[y], edge{x, i})
	}

	revs := make([]bool, n-1)
	// 返回是否需要翻转 x-fa 这条边
	var dfs func(int, int) bool
	dfs = func(x, fa int) bool {
		rev := start[x] != target[x] // x-fa 是否要翻转
		for _, e := range g[x] {
			y := e.to
			if y != fa && dfs(y, x) {
				revs[e.i] = true // 需要翻转 y-x
				rev = !rev       // x 被翻转了
			}
		}
		return rev
	}

	if dfs(0, -1) { // 只剩下一个根节点需要翻转，无法操作
		return []int{-1}
	}

	for i, rev := range revs {
		if rev {
			ans = append(ans, i)
		}
	}
	return
}

func main() {
	n := 7
	edges := [][]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {3, 5}, {1, 6}}
	start := "0011000"
	target := "0010001"
	result := minimumFlips(n, edges, start, target)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def minimumFlips(n: int, edges: List[List[int]], start: str, target: str) -> List[int]:
    class Edge:
        def __init__(self, to: int, idx: int):
            self.to = to
            self.idx = idx
    
    g = [[] for _ in range(n)]
    for i, e in enumerate(edges):
        x, y = e[0], e[1]
        g[x].append(Edge(y, i))
        g[y].append(Edge(x, i))
    
    revs = [False] * (n - 1)
    
    # 返回是否需要翻转 x-fa 这条边
    def dfs(x: int, fa: int) -> bool:
        rev = start[x] != target[x]  # x-fa 是否要翻转
        for e in g[x]:
            y = e.to
            if y != fa and dfs(y, x):
                revs[e.idx] = True  # 需要翻转 y-x
                rev = not rev  # x 被翻转了
        return rev
    
    if dfs(0, -1):  # 只剩下一个根节点需要翻转，无法操作
        return [-1]
    
    ans = []
    for i, rev in enumerate(revs):
        if rev:
            ans.append(i)
    return ans


def main():
    n = 7
    edges = [[0, 1], [1, 2], [2, 3], [3, 4], [3, 5], [1, 6]]
    start = "0011000"
    target = "0010001"
    result = minimumFlips(n, edges, start, target)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <string>
#include <functional>

using namespace std;

vector<int> minimumFlips(int n, vector<vector<int>>& edges, string start, string target) {
    struct Edge {
        int to, i;
    };
    vector<vector<Edge>> g(n);
    for (int i = 0; i < edges.size(); ++i) {
        int x = edges[i][0], y = edges[i][1];
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }

    vector<bool> revs(edges.size(), false);

    // 返回是否需要翻转 x-fa 这条边
    function<bool(int, int)> dfs = [&](int x, int fa) -> bool {
        bool rev = (start[x] != target[x]); // x-fa 是否要翻转
        for (auto& e : g[x]) {
            int y = e.to;
            if (y != fa && dfs(y, x)) {
                revs[e.i] = true; // 需要翻转 y-x
                rev = !rev;       // x 被翻转了
            }
        }
        return rev;
    };

    if (dfs(0, -1)) { // 只剩下一个根节点需要翻转，无法操作
        return {-1};
    }

    vector<int> ans;
    for (int i = 0; i < revs.size(); ++i) {
        if (revs[i]) {
            ans.push_back(i);
        }
    }
    return ans;
}

int main() {
    int n = 7;
    vector<vector<int>> edges = {{0, 1}, {1, 2}, {2, 3}, {3, 4}, {3, 5}, {1, 6}};
    string start = "0011000";
    string target = "0010001";
    vector<int> result = minimumFlips(n, edges, start, target);
    for (int v : result) {
        cout << v << " ";
    }
    cout << endl;
    return 0;
}