Pick the root that needs the fewest edge reversals

You are given a tree with n nodes labeled 1 to n. Its n - 1 edges are directed: each edge (u, v) points from u to v. Ignoring direction, the edges connect all nodes into a tree.

You may pick any node as the root. Once the root is picked, every edge must point away from the root (from the endpoint closer to the root toward the one farther away). To get there you may reverse edges; each reversal costs 1.

Implement:

def min_root_reversals(n: int, edges: list[tuple[int, int]]) -> int

Return the minimum number of reversals over all choices of root.

Constraints

• 1 <= n <= 10^5
• len(edges) == n - 1, 1 <= u, v <= n, u != v
• At most one edge between any pair of nodes; the undirected edges form a tree.

Example 1

n = 4, edges = [(2, 1), (2, 3), (4, 3)]
-> 1

Rooted at 2, edges 2 -> 1 and 2 -> 3 already point away; 4 -> 3 must become 3 -> 4, so 1 reversal. Rooting at 4 also costs 1 (flip 2 -> 3). No root costs 0.

Example 2

n = 4, edges = [(2, 1), (3, 1), (4, 1)]
-> 2

Every edge points into node 1. Rooting at a leaf, say 2, keeps 2 -> 1 and flips the other two.

Aim for better than trying every root with a separate traversal. Be ready to return the cost for every root as well.