この問題は問題 \(P_1\) のように書くことが出来ます。

問題 \(P_1\) : \(N\) 頂点の木が与えられる。 \(K\) 箇所の特別な頂点 \(v_1, \ldots, v_K\) を適切に選び、\(\max_{1 \leq v \leq N} \min_{1 \leq i \leq K} dist\left(v, v_i\right)\)を最小化せよ。

問題 \(P_1\) の判定問題版として、問題 \(P_2\) を考えます。

問題 \(P_2\) : \(N\) 頂点の木が与えられる。 \(K\) 箇所の特別な頂点 \(v_1, \ldots, v_K\) を適切に選び、\(\max_{1 \leq v \leq N} \min_{1 \leq i \leq K} dist\left(v, v_i\right) \leq X\) と出来るか判定せよ。

問題 \(P_2\) : を高速に解くことが出来れば、答えを決め打つ二分探索により、問題 \(P_1\) を高速に解くことが出来ます。ここで、問題 \(P_3\) を考えます。

問題 \(P_3\): 「任意の頂点 \(u\) について、ある特別な頂点 \(v\) が存在し、 \(dist\left(u, v\right) \leq X\) 」という条件を満たす為に選ぶ必要がある特別な頂点の数の最小値を求めよ。

問題 \(P_3\) を解くことが出来れば、問題 \(P_3\) の答えが \(K\) 以下であったか否かを調べることにより、問題 \(P_2\) を解くことが出来ます。問題 \(P_3\) は、入力の木を適当に根付き木にした後、各頂点 \(v\) 毎に、その頂点を根とした部分木のみを見た際の

• 頂点 \(v\) からの距離が \(X\) 以下である特別な頂点が存在するならば、その距離の最小値
• 頂点 \(v\) からの距離が \(X\) 以下である特別な頂点が存在しないならば、距離 \(X\) 以内に特別な頂点が存在しないような頂点の中での、頂点 \(v\) からの距離の最大値
• 部分木内の特別な頂点の数

という情報を記録する木上の動的計画法により解くことが出来ます。

これより、問題 \(P_2\) は \(O\left(N\right)\) の時間計算量で解くことが出来ます。問題 \(P_1\) の答えは明らかに \(N\) 以下ですから、以上より、答えを決め打つ二分探索により、問題 \(P_1\) を \(O\left(N \log N\right)\) の時間計算量で解けました。