ZERO / HERO
Asking your children before you answer

DP on Trees

The analogy

Every node asks its children for their answers first, then combines them into its own. Because a tree has no loops, each node is asked exactly once, and answers flow cleanly upwards from the leaves to the root.

Visualizer

Answers flowing upward

step 1 / 9
A 10B 5C 8D 3E 7F 2G 9

A tree with a value at each node. Pick a set of nodes with the maximum total, but you may never pick a node AND its parent.maximum weight independent set on a tree

import sys
sys.setrecursionlimit(300000)

def max_independent_set(tree, root=0):
    # dp[node] = (best excluding node, best including node)
    def dfs(u, parent):
        excl, incl = 0, value[u]
        for v in tree[u]:
            if v == parent:
                continue
            ce, ci = dfs(v, u)
            excl += max(ce, ci)   # child free to do either
            incl += ce            # child must be excluded
        return excl, incl
    return max(dfs(root, -1))

def diameter(tree, root=0):
    best = 0
    def depth(u, parent):
        nonlocal best
        top2 = [0, 0]
        for v in tree[u]:
            if v == parent: continue
            d = depth(v, u) + 1
            top2 = sorted(top2 + [d])[-2:]   # two deepest
        best = max(best, top2[0] + top2[1])
        return top2[1]
    depth(root, -1)
    return best
Check yourself

Why does a second state dimension dp[node][0/1] appear so often in tree DP?