可以到达每一个节点的最少边反转次数-526互联

给你一个 n 个点的简单有向图（没有重复边的有向图），节点编号为 0 到 n - 1 。如果这些边是双向边，那么这个图形成一棵树。
给你一个整数 n 和一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示从节点 ui 到节点 vi 有一条有向边。
边反转指的是将一条边的方向反转，也就是说一条从节点 ui 到节点 vi 的边会变为一条从节点 vi 到节点 ui 的边。
对于范围 [0, n - 1] 中的每一个节点 i ，你的任务是分别独立计算最少需要多少次边反转，从节点 i 出发经过一系列有向边，可以到达所有的节点。
请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]表示从节点 i 出发，可以到达所有节点的最少边反转次数。

1. 换根dp

计算某一个节点需要的反转次数比较简单，经过一次dfs即可
要计算所有节点的反转次数，必然不能对每个点进行计算
而是根据上一次的结果，直接运算出当前结果

class Solution {
public:
    vector<int> minEdgeReversals(int n, vector<vector<int>> &edges) {
        vector<vector<pair<int, int>>> g(n);
        for (auto &e: edges) {
            int x = e[0], y = e[1];
            g[x].emplace_back(y, 1);
            g[y].emplace_back(x, -1); // 从 y 到 x 需要反向
        }

        vector<int> ans(n, 0);
        function<void(int, int)> dfs = [&](int x, int fa) { //从0跑一次深度优先，计算0开始的翻转次数
            for (auto &[y, dir]: g[x]) { //遍历相邻节点
                if (y != fa) { //不返回原路
                    ans[0] += dir<0; //计算需要翻转的次数
                    dfs(y, x);
                }
            }
        };
        dfs(0, -1);

        function<void(int, int)> reroot = [&](int x, int fa) {//换根dp
            for (auto &[y, dir]: g[x]) {
                if (y != fa) {
                    ans[y] = ans[x] + dir; // dir 就是从 x 换到 y 的「变化量」
                    reroot(y, x);
                }
            }
        };
        reroot(0, -1);
        return ans;
    }
};