Analyzing a tree
l Root tree, so cut                 subtree
l Use dynamic program up from leaves to
determine subtree cuts efficiently
l Given cuts at children of a node,
compute cut at parent
l Definitions:
» v¯ are nodes below v
» C(v¯) is value of cut at subtree v¯