Graph Theory37 sections · 1633 units
Open in Course

CSES 1674 Subordinates - Recurrence

Sum of child subtrees

For a leaf node: ext{size}[v] = 1 (no children, yourself). For an internal node: ext{size}[v] = 1 + sum_{c in ext{children}(v)} ext{size}[c]. You count yourself (11) plus all nodes in child subtrees. This recurrence is the foundation of subtree DP.

Process children first, then add their sizes. The base case handles leaves. The recursive case handles internal nodes. Together they cover all nodes in the tree.