Rerooting vs Brute Force (Why rerooting wins)

Brute force runs BFS from every node. Each BFS takes $O(n)$, so the total is $O(n^2)$. For $n = 200{,}000$, that is $4 \times 10^{10}$ operations. At $10^8$ operations per second, it takes $400$ seconds. Way too slow.

Rerooting does $2$ DFS passes, each $O(n)$. Total: $O(n)$. For $n = 200{,}000$, that is about $4 \times 10^5$ operations. It finishes in under a millisecond.

The speedup comes from reusing work. Each edge transition costs $O(1)$ instead of $O(n)$. You trade $n$ full DFS traversals for $n$ constant-time updates. That is an $n$-fold improvement.