Tracking Subtree Sizes

To know which child has the largest subtree, you need subtree sizes beforehand. Run a preprocessing DFS that computes size[v] for every node. This is subtree DP: size[v] = 1 + Σ size[c] for children $c$.

Once you have sizes, the main DFS can identify the heavy child in $O(\text{degree})$ time per node. Iterate children and pick the one with maximum size[c]. Total preprocessing is O(n).

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