By using binary search, we only need to check whether an integer \(K\) satisfy the conditions in the problem statement.

To make the problem clearer, let’s paint each edge black or white. An edge is painted black if the colors of its two endpoints are the same. Otherwise, it is painted white. Then all the black edges form some non-intersect paths (i.e. not sharing any vertex). In a path, the set of vertices painted in one color is consecutive, so the number of colors of the vertices only depends on the number of white edges in it.

Formally, the decision problem has been rephrased as follows:

You need to paint each edge black or white to satisfy the conditions below:

• For each vertex, there are at most \(2\) black edges adjacent to it.
• For any path, it contains at most \(K-1\) white edges.

Consider the length of black and white edges as \(0\) and \(1\), respectively. Then the second condition means that the diameter of the tree is no more than \(K-1\). Now we can use tree DP to solve the problem.

Let \(dp_{x,0/1}\) be the minimum possible value of the maximum distance from \(x\) to vertices in the subtree rooted at \(x\) (considering the whole tree as a rooted one), when the length of the edge between \(x\) and its parent is \(0\) or \(1\) and the diameter of the subtree rooted at \(x\) is at most \(K-1\).

Let the sons of \(x\) be \(y_1,y_2,\cdots,y_k\) such that \(dp_{y_{_1},1} \ge dp_{y_{_2},1} \ge \cdots \ge dp_{y_{_k},1}\).

Let \(C_i(1 \le i \le k)\) be the maximum distance from \(x\) to vertices in the subtree rooted at \(y_i\).

Consider the lengths of the edges between \(x\) and \(y_i\) to determine \(C\). At first, suppose all such edges have length \(1\), so \(C=[dp_{y_{_1},1}+1,dp_{y_{_2},1}+1,\cdots,dp_{y_{_k},1}+1]\). Then we have to choose a set \(S\) and for each element \(i\) in \(S\), replace \(C_i\) with \(dp_{y_{_i},0}\), indicating that the length of the edge between \(x\) and \(y_i\) changes to \(0\).

Instead of replacing \(C_i\) with \(dp_{y_{_i},0}\), we replace it with \(\min\{dp_{y_{_i},0},dp_{y_{_i},1}+1\}\). As a result, only \(S\) with maximum size need to be considered.

Note that only the maximum and the second maximum of the sequence \(C\) make a difference to the \(dp\) values. Specifically, to make sure that paths whose LCA is \(x\) have lengths of no more than \(K-1\), the sum of the maximum and the second maximum of \(C\) should be at most \(K-1\) and the \(dp\) values are defined as the maximum of \(C\). We won’t choose big elements for \(S\) since they don’t change the maximum or the second maximum.

For \(dp_{x,0}\), there can be at most one edge of length \(0\) (i.e. \(|S| \le 1\)) , so \(S\) has two cases: \(\{1\}\) or \(\{2\}\). (if an element of \(S\) is greater than \(k\), just ignore it)

Similarly, for \(dp_{x,1}\), \(|S| \le 2\) so \(S\) has three cases: \(\{1,2\}\), \(\{1,3\}\) or \(\{2,3\}\).

We have solved the original problem in \(O(N\log^2{N})\) time, which is fast enough to pass.

In fact, we can solve it in \(O(N\log{\log{N}})\) time — on the one hand, since we only need to consider few largest elements (i.e. \(y_1,y_2,y_3\) and \(y_4\) in this editorial), we can solve the decision problem in \(O(N)\) time without sorting the sequence, and on the other hand, the answer is at most \(O(\log{N})\) according to Heavy-Light Decomposition, so we only need to do binary search on the range \([1,2 \lfloor \log_2{N} \rfloor+1]\).

Sample code (C++) : https://atcoder.jp/contests/abc293/submissions/39890084. (time complexity: \(O(N\log^2{N})\) )