Think First

Before reading, adapt the rerooting pattern to directed edges:

$1.$ How do you compute the cost for node $1$ as root? (Hint: Count backward edges in DFS)

$2.$ When moving root from u to v, how does the cost change? (Hint: Depends on whether edge is u→v or v→u)

$3.$ Is this still $O(n)$ rerooting? Try to write dfs1(u, parent) to count backward edges, and dfs2(u, parent, up_cost) to adjust cost when rerooting. Think about the edge direction. Spend $1$ minute thinking.