Graph Theory37 sections · 1633 units
Open in Course

State Definition on Trees

What does dp[node] represent

Define what ext{dp}[ ext{node}] means precisely. Is it the count of nodes in the subtree?

The maximum value? A boolean? Clear state definition is critical. If you define ext{dp}[v] as "number of nodes in subtree rooted at vv", then every computation follows from that. Vague definitions lead to confusion when writing transitions. Write down your state in one sentence before coding. This saves hours of debugging.