Tree DP with Multiple States per Node
What You'll Learn
You'll learn how to track multiple DP values at each tree node to handle different constraints or choices within the same problem.
Why Multiple States?
So far, you've seen Tree DP where each node stores a single value (like "maximum sum ending here" or "diameter passing through this subtree"). But many tree problems require tracking several scenarios simultaneously at each node.
Think of it like a traveler who must decide at each city: "Should I stay overnight or just pass through?" Your DP needs to remember both the best route if they stay and the best route if they skip that city.
The Core Pattern
Instead of dp[node] = single_value, you maintain:
dp[node][state] = value_for_that_state
Each state represents a different constraint or decision:
- State 0: "We don't select this node"
- State 1: "We do select this node"
Or for path problems:
- State 0: "Path doesn't end here"
- State 1: "Path ends at this node"
- State 2: "Path passes through this node"
When You Need This
Use multiple states when:
- The problem has conflicting constraints (selected vs not selected)
- You need to track different path types (ending here, starting here, passing through)
- The answer depends on parent's choice affecting children differently
Example Intuition
For "Maximum Independent Set on Trees" (nodes can't select adjacent nodes), you track:
dp[node][0]: Best sum without including this nodedp[node][1]: Best sum including this node
The recurrence combines these states based on children's states.
Key Takeaway: Track multiple DP states per node when a single value can't capture all the decision scenarios or constraints your problem requires—each state represents a distinct "mode" for that subtree.