Walkthrough (Small tree example)

Consider a tree with $4$ nodes: edges ($1$,$2$), ($1$,$3$), ($3$,$4$). Run the down pass from root $1$.

size[4] = 1, down[4] = 0. size[3] = 2, down[3] = 0 + 1 = 1. size[2] = 1, down[2] = 0. size[1] = 4, down[1] = 0 + 1 + 1 + 2 = 4.

Now the up pass. answer[1] = 4. answer[2] = 4 + 4 - 2(1) = 6. answer[3] = 4 + 4 - 2(2) = 4. answer[4] = 4 + 4 - 2(1) = 6.

Verify by hand: from node $2$, distances are $1 + 2 + 3 = 6$. Correct. From node $3$, distances are $1 + 2 + 1 = 4$. Correct.