Sloth Naptime

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define pb push_back
#define vll vector<ll>
#define vi vector<int>
#define tests int t; cin >> t; while(t--)
using namespace std;

int n; ll timer = 0;
vector<vi> parents, tree;
vi vis, powers(20); vll tin, tout;

void markParents(int u = 1) {
    vis[u] = 1;
    tin[u] = timer++;
    for(int v : tree[u]) {
        if(!vis[v]) {
            parents[v][0] = u;
            markParents(v);
        }
    }
    tout[u] = timer++;
}

void addEdge(int u, int v) {
    tree[u].pb(v);
    tree[v].pb(u);
}

bool isAncestor(int u, int v) {
    if(u == v) return true;
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}

int parentAfterJump(int u, int j) {
    int bit = 0;
    while(j > 0) {
        if(u == -1) break;
        if(j%2) u = parents[u][bit];
        bit++; j /= 2;
    }
    return u;
}

int minJumps(int u, int v) {
    int k = 19, jump = 0;
    while(k >= 0) {
        int p = parents[v][k];
        if(!isAncestor(p, u) && p != -1) {
            v = p;
            jump += powers[k];
        }
        k--;
    }
    return jump+1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    tree.assign(n+1, vi());
    parents.assign(n+1, vi(20, -1));
    vis.assign(n+1, 0);
    tin.assign(n+1, 0);
    tout.assign(n+1, 0);
    powers[0] = 1;
    for(int i = 1; i < 20; i++) powers[i] = 2*powers[i-1];
    for(int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        addEdge(u, v);
    }
    markParents();
    for(int i = 1; i < 20; i++) {
        for(int j = n; j >= 1; j--) {
            if(parents[j][i-1] == -1) continue;
            parents[j][i] = parents[parents[j][i-1]][i-1];
        }
    }
    tests {
        int a, b; ll c; cin >> a >> b >> c;
        if(isAncestor(b, a)) {
            int jumps = minJumps(b, a);
            if(c >= jumps) {
                cout << b << "\n";
            } else {
                cout << parentAfterJump(a, c) << "\n";
            }
        } else if(isAncestor(a, b)) {
            int jumps = minJumps(a, b);
            if(c >= jumps) {
                cout << b << "\n";
            } else {
                cout << parentAfterJump(b, jumps-c) << "\n";
            }
        } else {
            int jumps1 = minJumps(b, a), jumps2 = minJumps(a, b);
            if(jumps1 > c) {
                cout << parentAfterJump(a, c) << "\n";
            } else if(jumps1+jumps2 > c) {
                cout << parentAfterJump(b, jumps1+jumps2-c) << "\n";
            } else {
                cout << b << "\n";
            }
        }
    }
    return 0;
}