CONCEPT · Grandmaster
DP on trees
also reroot · tree knapsack
State lives on a subtree, maybe with a flag (matched / not). Reroot with a second DFS when every node must be the root once.
Intuition
Children are independent once you root. Combine them like knapsack items; the parent is not a child.
When to reach for it
- Subtree sizes, independent set, matching
- CSES Tree Matching / Tree Distances II
- Knapsack where items are subtrees
Usual pits
- Recursing into the parent
- Assuming size[v]/2 is a matching
- n reroots instead of one up-pass