Tree DP

Tree DP solves every subtree from its children's answers. A post-order DFS handles the children first, so each node just combines what's below it.

Pattern	What each node returns	Example
Pair state	Best with the node taken, and without	Non-adjacent sum on a tree
Return vs track	Best one-armed path, global best kept aside	Maximum path sum
Rerooting	A second pass hands down the parent's side	Distances from every node

The common trap is treating the value a node returns to its parent as the final answer. A path that bends through a node can use two of its child branches, but a path continuing up to the parent can only use one, so you return the best single-branch path upward while updating the best two-branch path in a separate variable. When every node needs the answer as if it were the root, a second top-down pass hands each child the contribution from the rest of the tree in $O(n)$ total time.

Approach	Time	Extra space
Brute force over choices	$O(2^n)$	$O(n)$
Rerun the DFS from every root	$O(n^2)$	$O(n)$
Post-order pass, then rerooting	$O(n)$	$O(n)$

Use it when the input is a tree and a node's answer depends on its subtree, like the best set of nodes, the heaviest path, or a total from every node.

The problems below start with the take-or-skip pair on a tree, move through a matched flag and rerooting, and end with a path sum that returns one value and tracks another.