We can prove that if a candidate is selected, no broken roads will be below his city in the tree. If there were, the candidate directly below that broken road would need to be selected, covering both the corresponding broken road and our initially selected candidate's broken road, making our initial candidate unneeded. This is a contradiction, as we want as few candidates as possible.

Therefore, all we have to do is DFS down the tree and mark down what candidate was last seen in each branch and the candidates that were replaced by another candidate lower than him. The answer is just the candidates that are in the last seen branch and not in the replaced branch.

Note that if a candidate is below another one, the upper candidate cannot possibly be in the answer, as if there were another branch that didn't have a replacing candidate, no candidate would be needed for this branch anyways.

18728585

An-other solution : 
It is easy to see that for optimal solution we can choose a subset of leaves of the tree. 
Traverse from the leaf nodes (size == 1 and number != 1) upto the node 1. This will give you how many (if any) bad roads a leaf node can cover. To avoid timeout, mark the visited nodes and traverse only upto a marked node. But this may give wrong answer in cases like this : 
4
1 2 2
2 3 1
2 4 2
To avoid this traverse the leaf nodes in decreasing order of the number of bad roads it covers.
Edit : 18728599

Thanks a lot everyone :D