木の直径を \(D\)、直径の端点を \(x,y\) とします。

\(x,y\) が同色の場合、明らかによさは \(D\) です。以降、\(x\) が白、\(y\) が黒の場合のみを考えます。 重要な事実として \(x\) から白色の頂点への距離が \(X\) であるようなものが存在します。\(y, Y\) についても同様です。 これは \(x,y\) が直径の端点であることから証明可能です。

よって、頂点 \(x,y\) からの距離のみが重要であり、他の頂点同士の距離は考慮する必要はありません。 ここから、よさが \(d\) 以下になるような色の塗り方の個数は \(x\) からの距離も \(y\) からの距離も \(d\) より大きいものが存在するなら \(0\)、そうでなければ \(x,y\) からの距離が共に \(d\) 以下であるような頂点の個数を \(k\) として \(2^{k}\) 通りであることがわかります。

これらから全ての塗り方に対する良さを求めることができます。 これは \(O(N)\) で実行可能で十分高速です。