Total Depth — Solution & Editorial

Back to the Problem

One BFS/DFS accumulating depths — a warm-up for the rerooting technique.

Complexity: O(N)

Watch out: The total reaches ~5×10⁹ on a path — 64-bit.