Since it is a tree problem, we will need to know its root, and part of the problem is to determine the root. Therefore, we will assume root exists (swap known with unknown), and try to find the best answer

Also, when we are traversing, due to the indirect nature of the graph, we need to know where we are from to avoid going back to visited nodes.

The interesting case is when root has more than 2 children. Let us swap unknown with known again, assume we picked 2 children, when can we do to improve solution? => we try to use exchange proof here.

i.e, if we keep n2 instead of n1, the overall cost change is

 -costK(n1) + costD(n1) - costD(n2) + costK(n2)

costK: cost to keep node and form a full binary tree rooted at that node costD: cost to delete that node, i.e.,size of the tree rooted at that node

Note that the “score” we have is in a delta form, and we want to get extreme value of it, then we should try another direction! max the # of surviors all the way, so we can avoid calculating costD, since it is boxed at N at the root level, and the recusive relation becomes straightforward