Let \(L\) and \(R\) be the both ends of the diameter of the tree. Then, for any vertex \(u\), either \(L\) or \(R\) is the furthest point from \(u\). We will prove it by contradiction:

Let us denote by \(d(u, v)\) the distance between Vertices \(u\) and \(v\). Suppose that there are vertices \(A\) and \(B\) such that \(d(A, B) \gt \max (d(A, L), d(A, R))\).

Let \(a\) be the LCA (Lowest Common Ancestor) of \(L\) and \(R\) when the tree is considered a tree rooted at \(A\). Similarly, let us define \(b\) for \(B\). We may assume that \(L, a, b, R\) occurs in this order in the diameter. Then, \(d(A, a) + d(a, b) + d(b, B) \geq d(A, B) \gt d(A, R) = d(A, a) + d(a, R)\), so \(d(a, b) + d(b, B) \gt d(a, R)\), thus \(d(L, B) = d(L, a) + d(a, b) + d(b, B) \gt d(L, a) + d(a, R) = d(L, R)\), which is a contradiction.

Therefore, for each query, we may narrow down the candidates of the answer to those on the shortest path from \(U_i\) to \(L\), or those from \(U_i\) to \(R\).

The problem of “finding the vertex when you advance from \(U_i\) towards \(X\) by distance \(K_i\)” can be boiled down to the Level Ancestor Problem on a rooted tree. The Level Ancestor Problem is a problem that asks to find, given \(u\) and \(d\), find the ancestor of \(u\) with depth \(d\).
By reading the queries beforehand, we may solve the problem as follows:

Do DFS (Depth-First Search) from the root to manage the vertices on the path from the root to the current vertex. This can be achieved by, when entering a vertex, appending it to an array, and when exiting, removing the last element of the array.

The ancestor of \(u\) with depth \(d\) is the \(d\)-th element of the managed array when entering \(u\).

In order to find \(L\) and \(R\), we may perform BFS or DFS twice; then, we need to solve Level Ancestor Problem twice. Thus, the problem has been solved in a total of \(O(N + Q)\) time.

Sample code (C++)