int LOGN = 19; int n; int timer = 0; vector adj[300005]; bool vis[300005]; int p[300005], tin[300005], tout[300005]; vector d(300005,0); int dp[300005][20];

void dfs(int v, int parent) { tin[v] = ++timer; if (parent != -1) d[v] = d[parent] + 1; p[v] = parent; dp[v][0] = parent; for (int i = 1; i < LOGN; i++){ if (dp[v][i — 1] == -1) dp[v][i] = -1; else dp[v][i] = dp[dp[v][i — 1]][i — 1]; } for (auto u : adj[v]){ if (u != parent) dfs(u, v); } tout[v] = ++timer; } bool isAncestor(int p, int c){ // check if p is ancestor of c return (tin[p] <= tin[c] && tout[p] >= tout[c]); } int lift(int v, int steps) //find the y-th ancestor of x { for (int i = 0; i < 19; ++i){ if ((1 << i) & steps){ v = dp[v][i]; if (v == -1) return -1; steps -= (1 << i); } } return v; } int LCA(int u, int v) { if (isAncestor(u, v)) return u; if (isAncestor(v, u)) return v; for (int i = 18; i >= 0; i--) { if (dp[u][i] == -1)// -1 should not be passed continue; if (!isAncestor(dp[u][i], v)) u = dp[u][i]; } return dp[u][0]; } void solve() { cin>>n; timer=0; for(int i=0;i<n-1;i++){// Input int x,y; cin>>x>>y; x--;y--; adj[x].pb(y); adj[y].pb(x); } dfs(0,-1); tout[0]=++timer; int q; cin>>q; for(int z=0;z<q;z++){ int u,v,energy; cin>>u>>v>>energy; u--;v--; if(isAncestor(u,v))// u is ancestor of v { if(d[v]-d[u]<=energy)// reachable cout<<v+1<<endl; else{// midway: lift int res=lift(v,energy); cout<<res+1<<endl; } } else if(isAncestor(v,u))// v is ancestor of u { if(d[u]-d[v]<=energy)// reachable cout<<v+1<<endl; else{/// midway: lift int res=lift(u,d[u]-d[v]-energy); cout<<res+1<<endl; } } else{ int lca=LCA(u,v); int dist=d[u]+d[v]-2*d[lca]; if(energy>=dist) cout<<v+1<<endl; else{ // find vertex of the path from u to v with distance of energy from u int dist1=d[u]-d[lca]; int dist2=d[v]-d[lca]; // lies on the path from u to LCA if(energy<=dist1){ int res=lift(u,energy)+1; cout<<res<<endl; } // lies on the path from LCA to v else{ int rem=energy-dist1; dist2-=rem; int res=lift(v,dist2)+1; cout<<res<<endl; } } } } } signed main() { FAST; solve(); return 0; }