Lời giải

Gọi ~lca(a, b)~ là đỉnh xa gốc nhất mà là tổ tiên của ~a~ và ~b~.
Gọi ~dist(a, b)~ là số cạnh trong đường đi ngắn nhất từ ~a~ đến ~b~.
Gọi ~d(u)~ là số cạnh trong đường đi từ gốc tới đỉnh ~u~.

Đặt ~x = lca(a, b)~.
Ta có thể chia bài toán thành 3 trường hợp:

• ~dist(a, b) \le c~: Tức khoảng cách từ ~a~ đến ~b~ bé hơn hoặc bằng ~c~, thì chú lười sẽ đến được đỉnh ~b~ và dừng lại.
• ~1 \le c \le dist(a, x)~: Tức vị trí chú lười dừng lại sẽ nằm trên đường đi từ ~a~ tới ~x~, cụ thể là tổ tiên thứ ~c~ của ~a~.
• ~dist(a, x) < c < dist(a, b)~: Tức vị trí chú lười dừng lại sẽ nằm trên đường đi từ ~b~ tới ~x~, cụ thể là tổ tiên thứ ~dist(a, b) - c~ của ~b~.

Bài toán của chúng ta là giờ tìm cách để tìm tổ tiên thứ ~k~ của một đỉnh ~u~ và ~lca(a, b)~ một cách hiệu quả. Ta có thể sử dụng kĩ thuật bước nhảy nhị phân (binary lifting) để giải cả hai bài toán này. Kĩ thuật được miêu tả sau đây:

Đầu tiên, ta dựng một mảng hai chiều ~up~ với ~up[i][j]~ là tổ tiên thứ ~2^j~ của đỉnh ~i~. Để xây được mảng này ta nhận thấy rằng ~up[i][j] = up[up[i][j - 1]][j - 1]~ nên dfs một lần qua cây là có thể dựng được. Độ phức tạp: ~\mathcal{O}(n\log{}n)~.

• Để tìm tổ tiên thứ ~k~ của đỉnh ~u~ ta duyệt qua các bit của ~k~, nếu bit thứ ~i~ của ~k~ bật thì t gán ~u = up[u][i]~. Dễ nhận thấy ~u~ là đáp án của bài toán.
  Độ phức tạp: ~\mathcal{O}(\log{}n)~.
• Để xác định ~lca(a, b)~ ta thực hiện các bước sau:
  • Giả sử ~d(a) > d(b)~, ta thay a bằng tổ tiên thứ ~d(a) - d(b)~ của a. Khi này, ~d(a) = d(b)~.
  • Ta thay ~a~ và ~b~ bằng hai đỉnh tổ tiên tương ứng sao cho ~d(a) = d(b)~ cho đến khi ~a = b~. Ta sẽ sử dụng mảng ~up~ để làm điều này một cách hiệu quả. Đỉnh ~a~ khi này sẽ là kết quả của bài toán.
    Độ phức tạp: ~\mathcal{O}(\log{}n)~.

Tổng độ phức tạp: ~\mathcal{O}(n\log{}n + q\log{}n)~.

Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

int n, q, d[N], up[N][19];
vector<int> adj[N];

void pre_dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i <= 18; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (int v : adj[u]) if (v != p) {
        d[v] = d[u] + 1;
        pre_dfs(v, u);
    }
}

int lift(int u, int k) {
    for (int i = 18; i >= 0; i--)
        if (k >> i & 1) {
            u = up[u][i];
        }
    return u;
}

int lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    v = lift(v, d[v] - d[u]);

    if (u == v) return u;

    for (int i = 18; i >= 0; i--)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }

    return up[u][0];
}

signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    pre_dfs(1, 0);

    cin >> q;
    for (int a, b, c; q--; ) {
        cin >> a >> b >> c;
        int x = lca(a, b);

        int dist = d[a] + d[b] - 2 * d[x];

        if (dist <= c) {
            cout << b << '\n';
        } else if (c <= d[a] - d[x]) {
            cout << lift(a, c) << '\n';
        } else {
            cout << lift(b, dist - c) << '\n';
        }
    }
}