Uber 有向树翻转边：一次遍历求所有根的代价

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 忽略边的方向后，输入是 n 个节点、n−1 条边的树；可翻转每条有向边。
• 对每个候选根，求使该根沿边方向能够到达所有节点所需的最少翻转数。
• 节点编号为 0 到 n−1；非法端点、环或不连通输入报错。

解题路线

1. 先把有向边变成双向邻接：沿原方向走的代价为 0，逆原方向走的代价为 1。以 0 为根遍历，累加 0 到各子节点的边代价。
2. 将根从父节点 u 移到相邻子节点 v 时，其余边相对根的方向不变，只有 (u,v) 这一条边的需求反过来。
3. 若原边 u→v，换根后要多翻一次，answer[v]=answer[u]+1；若原边 v→u，则少翻一次。遍历树即可填满所有答案。

手动走一遍

三点链 0→1←2：以 0 为根需翻转 2→1，代价 1；以 1 为根要翻转两条边，代价 2；以 2 为根同样只需翻转 0→1，代价 1。答案 [1,2,1]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def reversals_for_each_root(node_count, directed_edges):
    """For each tree root, count reversals needed to reach every node."""
    if node_count <= 0 or len(directed_edges) != node_count - 1:
        raise ValueError("expected a tree with n-1 edges")

    graph = [[] for _ in range(node_count)]
    for source, target in directed_edges:
        if source == target or not (0 <= source < node_count and 0 <= target < node_count):
            raise ValueError("invalid edge")
        graph[source].append((target, 0))
        graph[target].append((source, 1))

    parent = [-1] * node_count
    parent[0] = 0
    order = [0]
    root_cost = 0
    for node in order:
        for neighbor, reversal_cost in graph[node]:
            if neighbor == parent[node]:
                continue
            if parent[neighbor] != -1:
                raise ValueError("input contains a cycle")
            parent[neighbor] = node
            order.append(neighbor)
            root_cost += reversal_cost
    if len(order) != node_count:
        raise ValueError("input is disconnected")

    answer = [0] * node_count
    answer[0] = root_cost
    for node in order:
        for neighbor, reversal_cost in graph[node]:
            if parent[neighbor] == node:
                answer[neighbor] = answer[node] + (1 if reversal_cost == 0 else -1)
    return answer

复杂度

建图、计算根 0 的代价、换根传递都各扫描 O(n) 个节点与边；时间 O(n)，邻接表、遍历顺序和答案数组占 O(n) 空间。

易错点与追问

容易失分的边界

• 先确认方向：根到所有点可达，与所有点流向根是相反的题。本文代码解决前者。
• 每换一个根都重新 DFS 会退化到 O(n²)；树上换根只需调整跨越的那条边。
• 输入必须是树；有环图里一次换根可能改变多条路径，当前递推不适用。

继续深挖

• 若只问最优根，计算所有 answer 后取最小值及对应节点即可。
• 若边翻转成本不同，换根时加减该边的具体成本，其余推理保持不变。