MIT
58
lRoot
tree, so cut subtree
lUse
dynamic program up from leaves to determine subtree cuts
efficiently
lGiven
cuts at children of a node, compute cut at parent
lDefinitions:
»v¯ are nodes below v
»C(v¯)
is value of cut at subtree v¯
Analyzing a tree
