The definition of score can be extended from paths to subtrees. For each score \(s = 0, 1, \ldots\), there exists a unique minimal subtree \(T_s\) achieving that score, which equals \(T_{s-1}\) with its leaves removed.

The minimum value of \(s\) for which \(T_s\) is a path is the minimum score, and at that point a unique minimal good path \(P^* = T_s\) is obtained.

A necessary and sufficient condition for a path to be a good path is that it contains \(P^*\), and by splitting into the case where \(P^*\) is an isolated vertex and the case where it is not, the answer can be found using techniques such as convolution.

The time complexity is \(O(N \log N)\).