Biết rằng đồ thị đã cho là một cây. Gọi ~L~ và ~R~ là 2 đỉnh lá thuộc đường kính của cây. Khoảng cách xa nhất từ đỉnh ~u~ đến một đỉnh bất kì bằng khoảng cách từ ~u~ đến ~L~ hoặc đến ~R~.

Chứng minh nhận xét trên bằng phương pháp phản chứng:

Gọi ~d(u,v)~ là khoảng cách từ đỉnh ~u~ đến đỉnh ~v~. Giả sử tồn tại 2 đỉnh ~A~ và ~B~ sao cho:

$$d(A,B) > max(d(A,L),d(A,R))$$.

Gọi ~a~ là LCA (tổ tiên chung gần nhất) của ~L~ và ~R~ khi chọn gốc của cây tại đỉnh ~A~. Tương tự với ~b~ tương ứng với đỉnh ~B~. Và vì ~a, b~ LCA của ~L~ và ~R~ nên cả ~a~ và ~b~ đều phải nằm trên đường đi từ ~L~ đến ~R~.

Giả sử ~L~, ~a~, ~b~, ~R~ lần lượt nằm trên đường kính của cây từ trái sang phải.

Khi đó:

$$d(A,a) + d(a,b) + d(b,B) \ge d(A,B) > d(A,R) = d(A,a) + d(a,R)$$

Suy ra:

$$d(a,b) + d(b,B) > d(a,R)$$

$$\Rightarrow d(L,B) = d(L,a) + d(a,b) + d(b,B) > d(L,a) + d(a,R) = d(L,R)$$ Mâu thuẫn với giả thiết.

Do đó, với mỗi truy vấn, ta sẽ thu hẹp phạm vi tìm kiếm, chỉ tìm trên đường đi ngắn nhất từ ~U_i~ đến ~L~ hoặc từ ~U_i~ đến ~R~. Từ đó bài toán trở thành "Tìm đỉnh cách ~U_i~ một khoảng ~K_i~ trên đường đi từ ~L~ hoặc ~R~ đến ~U_i~".

Ta có thể xử lí offline như sau:

• Thực hiện DFS từ gốc để quản lý các đỉnh trên đường đi từ gốc đến đỉnh hiện tại. Duy trì một mảng, khi xét tới một đỉnh, thêm đỉnh đó vào cuối mảng và khi kết thúc loại bỏ phần tử cuối của mảng.

• Tổ tiên bậc ~d~ của ~u~ là phần tử thứ ~d~ của mảng tính từ phần tử ~u~ trở về trước. Để tìm ~L~ và ~R~ ta có thể thực hiện BFS hoặc DFS hai lần, sau đó giải quyết bài toán Trên hai lần.

Như vậy, độ phức tạp của thuật toán là ~O(N+Q)~.

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    vector<vector<int>> graph(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    int Q;
    cin >> Q;
    vector<vector<pair<int, int>>> query(N);
    for (int i = 0; i < Q; ++i) {
        int u, k;
        cin >> u >> k;
        u -= 1;
        query[u].emplace_back(i, k);
    }
    auto get_farthest = [&](int src) {
        vector<int> dist(N, N);
        queue<int> que;
        auto push = [&](int u, int d) {
            if (dist[u] > d) {
                dist[u] = d;
                que.push(u);
            }
        };
        push(src, 0);
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            for (int v : graph[u]) {
                push(v, dist[u] + 1);
            }
        }
        return max_element(dist.begin(), dist.end()) - dist.begin();
    };
    int L = get_farthest(0);
    int R = get_farthest(L);
    vector<int> ans(Q, -1);
    for (int root : {L, R}) {
        vector<int> path;
        auto dfs = [&](auto&& dfs, int u, int p) -> void {
            for (const auto& [q, k] : query[u]) {
                if (k <= (int)path.size()) {
                    ans[q] = path[(int)path.size() - k] + 1;
                }
            }
            path.push_back(u);
            for (int v : graph[u]) {
                if (v != p) {
                    dfs(dfs, v, u);
                }
            }
            path.pop_back();
        };
        dfs(dfs, root, -1);
    }
    for (int x : ans) {
        cout << x << '\n';
    }
    return 0;
}