Your dynamic programming strategy is correct. However, you are not constructing the tree correctly. In particular, the way you choose the root node, there are no guarantees of reaching all nodes in the tree, when starting from the root.
For instance, your code fails for,
7
1 2
1 3
4 2
5 4
6 4
7 4
(outputs a 1, where the correct answer is 2)