Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 834 Sum of Distances in Tree - Key Observation

Moving the root

When you move the root from node pp to its child cc:

1.1. Nodes in cc's subtree get 11 closer (they're now below the root instead of 22 edges away).

2.2. All other nodes get 11 farther (they have to go through cc now). If cc's subtree has count[c]\text{count}[c] nodes, then ncount[c]n - \text{count}[c] nodes get farther. So: answer[c]=answer[p]count[c]+(ncount[c])=answer[p]+n2count[c]\text{answer}[c] = \text{answer}[p] - \text{count}[c] + (n - \text{count}[c]) = \text{answer}[p] + n - 2 \cdot \text{count}[c].