Implementation Notes (Array indexing)

When implementing for LeetCode ($0$-indexed), root the tree at node $0$ instead of node $1$. Your adjacency list uses indices $0$ through $n-1$. The down pass DFS starts at dfs1(0, -1) and the up pass at dfs2(0, -1).

In the up pass, the formula stays: answer[v] = answer[u] + n - 2 * size[v]. No prefix-suffix arrays needed since sum is invertible (you subtract instead of needing to exclude).

Watch for the base case: size[v] = 1 for leaf nodes, down[v] = 0 for leaves. Initialize both arrays to zero before starting.