Think First

Before reading the solution, recall the rerooting template:

$1.$ Downward pass (DFS from root): Compute something for each subtree. What do you store? (Hint: Sum of distances and count of nodes in subtree)

$2.$ Upward pass (reroot): When moving root from u to child v, how does v's answer change? (Hint: Nodes in v's subtree get $1$ closer, nodes outside get $1$ farther)

$3.$ Final answer: Combine downward and upward information.

Try to write the two-pass structure: dfs1(u, parent) and dfs2(u, parent, up_value). What do you pass in up_value? Think for $1$ minute.