Course contentsShow
← Computer Science
Lesson 954 of 2,87222. Dynamic ProgrammingFree lesson

Tree DP with Multiple States per Node

Tracking multiple DP values at each node representing different problem constraints or choices.

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 node
  • dp[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.