Dp-on-Trees

LeetCode 834 note: rerooting DP: compute subtree sizes and ans[0] with root 0, then push ans[child] = ans[parent] - size + (n - size) to every node

LeetCode 968 note: post-order greedy with three states per node: has a camera, covered, not covered; place a camera only when a child is uncovered, and add one if the root is left uncovered

LeetCode 687 note: DFS returns the longest same-value downward chain in edges, and each node updates the answer with left + right

LeetCode 1372 note: each node returns two values, the longest zigzag starting left and starting right; going left extends the left child’s start-right value

LeetCode 124 note: DFS returns the best downward chain and updates the answer with left chain + node + right chain at every node; drop negative chains

LeetCode 563 note: return subtree sums in post-order; each node’s tilt is the difference of its subtree sums, added to the answer

LeetCode 543 note: the diameter may skip the root; return heights in post-order while updating the answer with left + right height at every node, counting edges