题目传送门(BZOJ)

题解 :

每次询问先通过倍增求出LCA $t$,

然后判断$dep[u]+dep[v]-2\times dep[t]$,及$u$到$v$的长度是否大于给定的步数.

若大于等于, 则直接跳到$v$即可, 否则, 判断一下断点是在$u$到$t$的链上还是$t$到$v$的链上

直接通过倍增跳相应的步数即可.

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2; const int N = 1000011;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)struct Edge { int to; Edge *next;}*h[N], e[N<<1];int dep[N], f[20][N];inline void addEdge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}void dfs(int p) { dep[p] = dep[f[0][p]]+1; for(int i = 1; i <= 19; i ++ ) f[i][p] = f[i-1][f[i-1][p]]; rev(i, p) if(i->to != f[0][p]) { f[0][i->to] = p; dfs(i->to); }}int lca(int x, int y) { if(dep[x] < dep[y]) swap(x, y); for(int i = 19; ~i; i -- ) if(dep[f[i][x]] >= dep[y]) x = f[i][x]; if(x == y) return x; for(int i = 19; ~i; i -- ) if(f[i][x] != f[i][y]) x = f[i][x], y = f[i][y]; return f[0][x];}int jump(int x, int y) { for(int i = 19; ~i; i -- ) if((1<<i)<=y) x = f[i][x], y -= (1<<i); return x;}int main() { int n = rd(), p = rd(), Q = rd(); for(int i = 2; i <= n; i ++ ) { int u = rd(), v = rd(); addEdge(u, v); addEdge(v, u); } dfs(1); while(Q -- ) { int u = rd(), v = rd(), t = lca(u, p); if(dep[p]+dep[u]-2*dep[t] <= v) p = u; else if(dep[p]-dep[t] >= v) p = jump(p, v); else p = jump(u, dep[p]+dep[u]-2*dep[t]-v); printf("%d ", p); }}