DP on Trees

Concepts: pyTreeDP, pyMaxIndependentSet, pyTreeKnapsack

Tree DP is a post-order DFS where you compute the DP value for a node from the DP values of its children. The state depends on the subtree rooted at each node. Because the problem structure mirrors the tree structure, the recursion writes itself: solve for children first, then combine to solve for the parent. This naturally maps to functional aggregation in distributed computation trees. Maximum Independent Set on a Tree An independent set is a subset of nodes where no two adjacent nodes are selected. On a general graph this is NP-hard. On a tree it is solvable in O(n) with DP. dp[node][0] = max independent set size in the subtree of node, when node is NOT selected. dp[node][1] = same, when node IS selected. If node is not selected, children can be selected or not. If node is selected, chi