解を二分探索します。

直径を \(x\) 以下にできるかを木 dp によって判定します。

木 dp では、子供以下の集合において最も遠い頂点までの距離を記録します。

どの 2 つの距離の和も \(x\) を超えないように一部の辺を切ります。

これは、距離の集合をソートして後ろ二つの和が \(x\) を超える限り切っていけば良いです。

よって、\(O(N \log N \log CN)\) で答えが求まりました。

ところで、この問題は \(O(N \log CN)\) で解くこともできます。

距離の集合をソートするパートをより効率的に解くことができます。

\(y = ceil(x / 2)\) を超える距離は高々一つ、\(y\) 未満のものはいくつあってもよいという事実に着目することで、\(y\) 以上の最小値、\(y\) 未満の最大値を求めて場合分けすればよいです。