Notice that you are required to find paths ending in leaves (except one which is used to cover a single leaf ) that pass through a single common vertex. So you only need to root the tree at a suitable vertex such that the largest of the subtrees (in terms of the number of leaves) of the root does not exceed the sum of the others by more than 1.