<p>There is a <strong>simple directed graph</strong> with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>. The graph would form a <strong>tree</strong> if its edges were bi-directional.</p>

<p>You are given an integer <code>n</code> and a <strong>2D</strong> integer array <code>edges</code>, where <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> represents a <strong>directed edge</strong> going from node <code>u<sub>i</sub></code> to node <code>v<sub>i</sub></code>.</p>

<p>An <strong>edge reversal</strong> changes the direction of an edge, i.e., a directed edge going from node <code>u<sub>i</sub></code> to node <code>v<sub>i</sub></code> becomes a directed edge going from node <code>v<sub>i</sub></code> to node <code>u<sub>i</sub></code>.</p>

<p>For every node <code>i</code> in the range <code>[0, n - 1]</code>, your task is to <strong>independently</strong> calculate the <strong>minimum</strong> number of <strong>edge reversals</strong> required so it is possible to reach any other node starting from node <code>i</code> through a <strong>sequence</strong> of <strong>directed edges</strong>.</p>

<p>Return <em>an integer array </em><code>answer</code><em>, where </em><code>answer[i]</code><em> is the</em><em> </em> <em><strong>minimum</strong> number of <strong>edge reversals</strong> required so it is possible to reach any other node starting from node </em><code>i</code><em> through a <strong>sequence</strong> of <strong>directed edges</strong>.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><img height="246" src="https://assets.leetcode.com/uploads/2023/08/26/image-20230826221104-3.png" width="312" /></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[2,0],[2,1],[1,3]]
<strong>Output:</strong> [1,1,0,2]
<strong>Explanation:</strong> The image above shows the graph formed by the edges.
For node 0: after reversing the edge [2,0], it is possible to reach any other node starting from node 0.
So, answer[0] = 1.
For node 1: after reversing the edge [2,1], it is possible to reach any other node starting from node 1.
So, answer[1] = 1.
For node 2: it is already possible to reach any other node starting from node 2.
So, answer[2] = 0.
For node 3: after reversing the edges [1,3] and [2,1], it is possible to reach any other node starting from node 3.
So, answer[3] = 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><img height="217" src="https://assets.leetcode.com/uploads/2023/08/26/image-20230826225541-2.png" width="322" /></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[1,2],[2,0]]
<strong>Output:</strong> [2,0,1]
<strong>Explanation:</strong> The image above shows the graph formed by the edges.
For node 0: after reversing the edges [2,0] and [1,2], it is possible to reach any other node starting from node 0.
So, answer[0] = 2.
For node 1: it is already possible to reach any other node starting from node 1.
So, answer[1] = 0.
For node 2: after reversing the edge [1, 2], it is possible to reach any other node starting from node 2.
So, answer[2] = 1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= u<sub>i</sub> == edges[i][0] &lt; n</code></li>
	<li><code>0 &lt;= v<sub>i</sub> == edges[i][1] &lt; n</code></li>
	<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>
	<li>The input is generated such&nbsp;that if the edges were bi-directional, the graph would be a tree.</li>
</ul>

# region rerooting
from typing import Callable, List, Literal

Op = Callable[[int, int, int, Literal[0, 1]], int]
Merge = Callable[[int, int], int]
E = Callable[[int], int]


class Rerooting:

    __slots__ = ("adjList", "_n", "_decrement", "_root", "_parent", "_order")

    def __init__(self, n: int, decrement: int = 0):
        """n是顶点数， decrement是1-index 或者 0-indexed，默认1-index"""
        self._n = n
        self.adjList = [[] for _ in range(n)]
        self._root = None  # 最初遍历时的根
        self._decrement = decrement

    def add_edge(self, u: int, v: int):
        """添加一条无向边"""
        u -= self._decrement
        v -= self._decrement
        self.adjList[u].append(v)
        self.adjList[v].append(u)

    def rerooting(self, op: Op, merge: Merge, e: E, root: int = -1) -> List[int]:
        # step1
        if root == -1:
            root = 0
        else:
            root -= self._decrement
        assert 0 <= root < self._n
        self._parent = parent = [-1] * self._n  # 记录父亲结点
        self._root = order = [root]  # 记录dfs序，深度单调增加
        stack = [root]
        while stack:
            from_node = stack.pop()
            for to_node in self.adjList[from_node]:
                if to_node == parent[from_node]:
                    continue
                parent[to_node] = from_node
                order.append(to_node)
                stack.append(to_node)
        # step2
        dp1 = list(map(e, range(self._n)))
        dp2 = list(e(i) for i in range(self._n))
        for from_node in order[::-1]:
            t = e(from_node)
            for to_node in self.adjList[from_node]:
                if parent[from_node] == to_node:
                    continue
                dp2[to_node] = t
                t = merge(t, op(dp1[to_node], from_node, to_node))
            t = e(from_node)
            for to_node in self.adjList[from_node][::-1]:
                if parent[from_node] == to_node:
                    continue
                dp2[to_node] = merge(t, dp2[to_node])
                t = merge(t, op(dp1[to_node], from_node, to_node))
            dp1[from_node] = t
        # step3
        for new_root in order[1:]:  # 把最终结果放入dp1，res[u] = merge(dp1[u], dp2[u])
            par = parent[new_root]
            dp2[new_root] = op(merge(dp2[new_root], dp2[par]), new_root, par)
            dp1[new_root] = merge(dp1[new_root], dp2[new_root])
        return dp1


# endregion rerooting


class Solution:
    def minEdgeReversals(self, n: int, edges: List[List[int]]) -> List[int]:
        book, rt = dict(), Rerooting(n)

        for u, v in edges:
            rt.add_edge(u, v)
            book[u, v] = 0
            book[v, u] = 1

        return rt.rerooting(lambda c, u, v: c + book[u, v], add, lambda _: 0)
1828