木の直径の両端の頂点を \(L, R\) とおきます。このとき、任意の頂点 \(u\) に対し、\(L,R\) のいずれかは \(u\) から最も遠い点です。このことを背理法で示します。

頂点 \(u, v\) の距離を \(d(u, v)\) で表すことにする。ある頂点 \(A, B\) が存在して、\(d(A, B) \gt \max (d(A, L), d(A, R))\) であると仮定する。

\(A\) を根とした根付き木における、\(L, R\) の LCA を \(a\) とおく。同様に \(B\) に対して \(b\) を定める。直径において \(L, a, b, R\) はこの順に並んでいるとしてよい。このとき、\(d(A, a) + d(a, b) + d(b, B) \geq d(A, B) \gt d(A, R) = d(A, a) + d(a, R)\) から \(d(a, b) + d(b, B) \gt d(a, R)\) となり、\(d(L, B) = d(L, a) + d(a, b) + d(b, B) \gt d(L, a) + d(a, R) = d(L, R)\) となるので矛盾。

よって、各クエリについて、\(U_i\) から \(L\) までの最短パス上か、\(U_i\) から \(R\) までの最短パス上の頂点のみを答えの候補として考えればよいです。

「 \(U_i\) から \(X\) に向かって距離 \(K_i\) だけ進んだ頂点を求める」という問題は、頂点 \(X\) を根とした根付き木における Level Ancestor Problem に帰着することができます。Level Ancestor Problem とは、\(u, d\) が与えられたとき、\(u\) の祖先であって深さが \(d\) であるものを求める問題です。
クエリを先読みしておくことで、次のように解くことができます。

根から DFS を行い、根から現在いる頂点までのパス上の頂点を管理する。これは DFS で頂点に入るときに配列の末尾に追加し、頂点から出るときに配列の末尾の頂点を取り除けばよい。

\(u\) の祖先であって深さが \(d\) であるものは、\(u\) に入った時点で管理している頂点列の \(d\) 番目の要素である。

\(L, R\) を求めるには BFS や DFS を二回行えばよく、その後は \(L, R\) を根として Level Ancestor Problem を二回解けばよいので、元の問題を \(O(N + Q)\) で解くことができました。

実装例 (C++)