Problem - Tree Distances II (CSES 1133)

Here is your first rerooting problem. Given a tree of $n$ nodes, compute the sum of distances from each node to all other nodes. The distance between two nodes is the number of edges on the path between them.

Input: first line is $n$. Next $n - 1$ lines each have two integers $a$ and $b$ describing an edge. Output: $n$ integers, where the $i$-th integer is the sum of distances from node $i$ to every other node.

Brute force runs a BFS from each node in $O(n^2)$. You need $O(n)$ using rerooting. Think about what changes when you shift the root from $u$ to child $v$.