State Compression for Tree DP
What you'll learn: How to use bitmasks to efficiently track multiple boolean properties at each tree node during dynamic programming computations.
The Core Challenge
When solving tree DP problems, you sometimes need to track several yes/no properties at each node—like "Is this node colored red?", "Is this node included in the solution?", or "Has this subtree been visited?". Storing each property separately wastes memory and clutters your state definition.
What is State Compression?
State compression uses bitmasks to pack multiple boolean flags into a single integer. Each bit position represents one property: bit 0 might mean "node is active," bit 1 might mean "node is locked," and so on.
Instead of dp[node][isActive][isLocked][isMarked], you write dp[node][mask] where mask is an integer encoding all three properties.
How It Works
Think of a bitmask as a compact checklist. If you have 4 properties to track:
mask = 0b1011means properties 0, 1, and 3 are true; property 2 is false.- Setting bit 2:
mask |= (1 << 2)→0b1111 - Checking bit 1:
if (mask & (1 << 1))→ true - Clearing bit 3:
mask &= ~(1 << 3)→0b0111
Why It Matters for Tree DP
State compression dramatically reduces memory usage when you have many boolean dimensions. A state with 10 boolean flags would normally require a 10-dimensional array—impractical! With bitmasks, you just need one extra dimension holding integers from 0 to 1023 (2¹⁰−1).
This technique is essential for problems like "tree coloring with constraints" or "selecting nodes with multiple restrictions," where each node's state depends on several independent conditions inherited from its subtree.
Key Takeaway: State compression uses bitmasks to encode multiple boolean properties as a single integer, making tree DP states compact and manageable when tracking several yes/no conditions per node.