Tree DP: Independent Set, Diameter, Rerooting

What This Concept Is

Rooting an undirected tree makes each edge a parent/child relationship. Child subtrees interact only through the parent boundary, so a small boundary state can suffice. Process children before their parent, typically with iterative traversal plus reversed discovery order. A general dependency graph is not automatically a tree: shared children and extra edges can invalidate decomposition.

Why It Matters Here

Tree DP demonstrates that a useful DP need not have repeated recursive calls. It also makes input validation part of correctness. The lab requires a simple, connected tree with n-1 edges; empty input is allowed by convention. Merely counting n-1 edges does not prove connectedness or absence of cycles.

Concrete Examples

Maximum-weight independent set. Let take[v] optimize the rooted subtree with v selected; skip[v] optimizes it with v excluded:

take[v] = weight[v] + sum(skip[c] for child c)
skip[v] = sum(max(take[c], skip[c]) for child c)

The chosen parent excludes every child. Otherwise each child can choose its better boundary state. Child subtrees have no cross edges, so combining their choices is feasible and exhaustive. Signed weights are allowed and the empty set is feasible. On the path with weights [4,10,4], the middle alone yields 10, better than both endpoints' 8. On all-negative weights, output is 0 and the empty set. Reconstruct top-down while carrying whether the parent is chosen. Time and storage are O(n) under unit-cost arithmetic, including input validation.

Diameter, unweighted edges. Define downward height as the largest number of edges from v to a descendant, with leaf height 0. The longest path whose highest vertex is v uses the two largest child heights plus their connecting edges, or fewer branches if necessary. Maximize this candidate over all vertices. Node-count and edge-count conventions differ by one for nonempty paths. Weighted negative-edge variants need a separate policy for empty paths and endpoints.

Rerooted distance sums. With unit edges, compute subtree sizes size[c] and S(root)=sum(depth). Moving the root over edge v->c makes size[c] vertices one step closer and all n-size[c] others one step farther: S(c)=S(v)+n-2*size[c]. On path 0-1-2, sums are [3,2,3]. One postorder and one preorder give all sums in O(n). More general rerooting requires a cheap way to exclude each child's contribution; recomputing all sibling combinations per child can be quadratic at a high-degree vertex.

Common Confusion / Misconceptions

A filesystem can contain links and a dependency graph can have shared nodes; the metaphor does not establish tree structure. Recursive pseudocode can overflow on a 2,500-vertex chain even when its asymptotic bound is linear. Root selection does not change the independent-set optimum, but can change a tied witness. Unweighted diameter formulas do not silently generalize to every weighted variant.

How To Use It

Validate the tree, define the boundary state and orient children once. Derive combination rules from edge constraints. Use iterative traversal when depth is unbounded by the contract. Independently verify selected vertices, no adjacent selection, objective sum and small-instance optimality by enumerating subsets. For rerooting, account for total work over all child exclusions.

Check Yourself

Why can child optima be summed here but not on an arbitrary graph? Why are n-1 edges insufficient validation? What makes the all-roots distance formula linear?

Mini Drill or Application

A star has center weight 7 and three leaves each weight 3. Find the independent set and all distance sums. Feedback: all leaves give value 9; center sum 3, each leaf sum 5. Explain both using boundary states rather than enumeration alone.

Read This Only If Stuck

Competitive Programming: tree DP and independent-set exercises. Treat rerooting as a derived extension after the core independent-set lab passes.