The key question: what information from a subtree do we need to make decisions at the parent? Common patterns: single value (subtree sum/max), pair (include/exclude), tuple (multiple mutually exclusive states).
If constraints involve parent-child relationships (no adjacent, must cover), you likely need multiple states per node. Test your state design: can you compute the parent's state from just the children's states? If yes, it's valid. If you need grandchildren info, add more states.