Subtree Size

For each node $v$, let size[v] be the size of its subtree, including $v$ itself. You compute this with a single DFS using the formula size[v] = 1 + Σ_u in children[v] size[u]. For a leaf, size[v] = 1 since it has no children. For an internal node, you add $1$ for the node itself plus the sizes of all child subtrees.

Subtree sizes determine which edges are heavy. Nodes with large subtrees get heavy edges. This computation takes $O(n)$ time, visiting each node once.

Space complexity is $O(n)$ for the data structures used.