The problem can be written as follows:

Problem \(P_1\): Given a tree with \(N\) vertices, choose \(K\) special vertices \(v_1, \ldots, v_K\) to minimize \(\max_{1 \leq v \leq N} \min_{1 \leq i \leq K} dist\left(v, v_i\right)\).

Let us modify it and consider the following decision problem:

Problem \(P_2\): Given a tree with \(N\) vertices, determine whethere it is possible to choose \(K\) special vertices \(v_1, \ldots, v_K\) so that \(\max_{1 \leq v \leq N} \min_{1 \leq i \leq K} dist\left(v, v_i\right) \leq X\).

If we can solve \(P_2\) fast, we can do a binary search for the answer to solve \(P_1\) fast. Now, let us consider the following problem:

Problem \(P_3\): Find the minimum number of special vertices required to satisfy the following condition: for every vertex \(u\), there is a special vertex \(v\) such that \(dist\left(u, v\right) \leq X\).

If we can solve \(P_3\), we can solve \(P_2\) by checking whether the answer to \(P_3\) is not greater than \(K\). Actually, we can solve it: let us make the tree rooted in some way and write dynamic programming on it where each vertex \(v\) stores the following information considering only the subtree rooted at \(v\):

• if there are special vertices whose distances from \(v\) is not greater than \(K\), the minimum among those distances;
• otherwise, the maximum distance from \(v\) to a vertex without a special vertex within the distance of \(X\);
• additionally, the number of special vertices in the subtree.

In this way, we can solve \(P_2\) in \(O\left(N\right)\) time. Since the answer to \(P_1\) is obviously not greater than \(N\), we can do a binary search for the answer to \(P_1\) to solve it in \(O\left(N \log N\right)\) time.