Two K Minus One

At most $2k - 1$ nodes: sort the key nodes by DFS order and add the LCA of each adjacent pair. Every added node is a branching point of the key set, and a tree with $k$ leaves has fewer than $k$ internal branchings. Construction is $\Theta(n)$ per query, rerunning the DFS.

At most $2k - 1$ nodes: sort the key nodes by DFS order and add the LCA of each adjacent pair. Every added node is a branching point of the key set, and a tree with $k$ leaves has fewer than $k$ internal branchings. Construction is $O(k \log n)$.

$\Theta(k \log n)$ nodes: sort the key nodes by DFS order and add the LCA of each adjacent pair. Every added node is an ancestor of some key node, and a tree of depth $\log n$ contributes one chain per key node. Construction is $O(k \log n)$.

At most $2k - 1$ nodes: sort the key nodes by DFS order and add the LCA of every pair. Every added node is a branching point of the key set, and a tree with $k$ leaves has fewer than $k$ internal branchings. Construction is $O(k^2 \log n)$.