We do binary search for the answer. Hereinafter, we consider whether the answer can be at most \(K\).

Take an arbitrary root to consider it as a rooted tree; we do tree DP (Dynamic Programming) on it. Let \(dp_v\) be the minimum possible maximum number of distinct colors of the vertices in a path from \(v\) to its ancestor. Also, let us define \(f_v\) by \(f_v = 1\) if, when the minimum is achieved, there are two children of \(v\) painted in the same color as \(v\) (i.e. if \(v\)’s parent cannot be painted in the same color as \(v\)), and \(f_0\) otherwise.

It does not decrease the maximum distinct colors on a simple path to increase the maximum distinct colors of the vertices in a simple path from \(v\) to its ancestor so that \(v\)’s parent is painted in the same color as \(v\).

Thus, we only have to consider the state where the maximum distinct colors of the vertices in a simple path from \(v\) to its parents is \(dp_v\) and where \(v\)’s parent can be painted in the same color as \(v\) if \(f_v = 0\) and cannot be if \(f_v = 1\).

Now we consider the transitions of the DP.
Let \(X\) be the descending sequence consisting of \(dp_w\) for all children \(w\) of \(v\) such that \(f_w = 0\), and \(Y\) be the descending sequence consisting of \(dp_w\) for all children \(w\) of \(v\) such that \(f_w = 1\). Also, let \(x\) be the length of the sequence \(X\), and \(y\) be the length of \(Y\). For each vertex \(v\), there are at most two children of \(v\) that are painted in the same color as \(v\), so we can divide into the following three cases:

• Case \(1\): no children of \(v\) is painted in the same color as \(v\).
• Case \(2\): one children of \(v\) is painted in the same color as \(v\).
• Case \(3\): two children of \(v\) is painted in the same color as \(v\).

Now we consider the optimal solution provided that the answer is at most \(K\).

First of all, if \(x = 0\), then the only possible case is case \(1\), while if \(x \neq 0\), we can choose case \(2\) instead of case \(1\) without worsening the situation, so all we have to do is to compare cases \(2\) and \(3\).

It is optimal to choose children \(w\) of \(v\) with the smallest \(dp_w\), so \(dp_v = \max (X_1,X_2+1,Y_1+1)\) for case \(2\) and \(dp_v = \max(X_1,X_2,X_3+1,Y_1+1)\) for case \(3\). (\(X\) or \(Y\) may not have enough number of elements, in which case we can exclude them from \(\max\).)

We now consider when to adopt case \(3\).
Obviously, \(x \geq 2\) is necessary, so we assume \(x \geq 2\).
Let sequence \(C\) be \((X_1 - 1, X_2, \ldots, X_x, Y_1, \ldots, Y_y)\) sorted in descending order, and sequence \(D\) be \((X_1 - 1, X_2- 1, \ldots, X_x, Y_1, \ldots, Y_y)\) sorted in descending order.
If case \(2\) is adopted, the answer turns out to be at least \(C_1 + C_2 + 1\); if case \(3\) adopted, the answer turns out to be at least \(D_1 + D_2 + 1\).
Here, since \(C_1 + C_2 + 1\geq D_1 + D_2 + 1\), we can determine that we choose case \(3\) if and only if \(\max (X_1,X_2+1,Y_1+1) > \max(X_1,X_2,X_3+1,Y_1+1)\) or \(C_1 + C_2 + 1 > K\).

Therefore, the decision problem has been solved.

In the discussion above, we sorted the sequence, but actually it need not be sorted, but we just have to take a constant number of largest elements, so the decision problem can be solved in an \(O(N)\) time. Considering the HL (Heavy-Light) decomposition, the answer is bounded by \(O(\log N)\), so the problem has been solved in a total of \(O(N \log \log N)\) time.