100041. 可以到达每一个节点的最少边反转次数

100041.可以到达每一个节点的最少边反转次数

题目描述：

给你一个 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 出发，可以到达所有节点的 最少边反转 次数。

数据范围：

$2\le n \le 10^5;u_i \neq v_i$

题解：

因为需要计算每个节点需要翻转的边的条数，因此可以考虑先把 $0$ 为树根的先算出来，然后将 $1$ 换到树根，那么就可得到 $1$ 的答案。

容易看出来是一个换根dp。换根dp，使用两个dfs，第一个dfs1先计算出来 $0$ 作为根的答案，然后用第二个dfs2。当遍历到 $u$ 时，访问 $u$ 的出边 $v$ 。尝试将 $v$ 换到树根，如果 $u\rightarrow v$ ，那么在计算 $u$ 的答案时，不会计入这条边，但是计算 $v$ 时需要计入这条边，因此 $ans[v] = ans[u] + 1$ 。同理可以得到另一种情况 $ans[v] = ans[u] - 1$ 。

代码：

auto optimize_cpp_stdio = []()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    struct Node
    {
        int v, w;
    };

    vector<vector<Node>> g;
    vector<int> ret;
    int down = 0, up = 0;
    int ans = 0;
    void dfs1(int u, int fa)
    {
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i].v, w = g[u][i].w;
            if (v == fa)
                continue;
            if (w == 1)
                down++;
            else
                up++;
            dfs1(v, u);
        }
    }
    void dfs2(int u, int fa)
    {
        for (int i = 0; i < g[u].size(); ++i)
        {
            int v = g[u][i].v, w = g[u][i].w;
            if (v == fa)
                continue;
            if (w == 1)
                ret[v] = ret[u] + 1;
            else
                ret[v] = ret[u] - 1;
            dfs2(v, u);
        }
    }
    vector<int> minEdgeReversals(int n, vector<vector<int>> &edges)
    {
        g.resize(n);
        ret.resize(n, 0);
        for (auto &edge : edges)
        {
            int u = edge[0], v = edge[1];
            g[u].push_back({v, 1});
            g[v].push_back({u, -1});
        }
        dfs1(0, -1);
        ret[0] = up;
        dfs2(0, -1);
        return ret;
    }
};