传送门

Code

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

#define RG register int
#define LL long long

template<typename elemType>
inline void Read(elemType& T) {
    elemType X = 0, w = 0; char ch = 0;
    while (!isdigit(ch)) { w |= ch == '-';ch = getchar(); }
    while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
    T = (w ? -X : X);
}

const int maxn = 300010;

struct Graph {
    struct edge { int Next, to; };
    edge G[maxn << 1];
    int head[maxn];
    int cnt;

    Graph() :cnt(2) {}
    void clear(int n) {
        cnt = 2;fill(head, head + n + 2, 0);
    }
    void add_edge(int u, int v) {
        G[cnt].to = v;
        G[cnt].Next = head[u];
        head[u] = cnt++;
    }
};
Graph G;
int N, M;

int Deep[maxn], Height[maxn], Anc[maxn][20], Top[maxn], Hson[maxn];
int highbit[maxn], MaxDeep[maxn];
vector<int> Up[maxn], Down[maxn], Path;

void DFS1(int u, int fa) {
    Anc[u][0] = fa;
    Height[u] = 1;
    for (int i = 1;i < 20;++i)
        Anc[u][i] = Anc[Anc[u][i - 1]][i - 1];
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == fa) continue;
        Deep[v] = Deep[u] + 1;
        DFS1(v, u);
        Height[u] = max(Height[u], Height[v] + 1);
        if (Height[Hson[u]] < Height[v]) Hson[u] = v;
    }
    return;
}

void DFS2(int u, int fa, int top) {
    Path.push_back(u);
    Top[u] = top;
    MaxDeep[top] = max(MaxDeep[top], Deep[u]);
    Down[top].push_back(u);
    if (Hson[u]) DFS2(Hson[u], u, top);
    for (int i = G.head[u];i;i = G.G[i].Next) {
        int v = G.G[i].to;
        if (v == fa || v == Hson[u]) continue;
        DFS2(v, u, v);
    }
    if (u == top) {
        int len = MaxDeep[top] - Deep[u] + 1;
        for (int i = Path.size() - 1;i >= max((int)Path.size() - len - 1, 0);--i)
            Up[top].push_back(Path[i]);
    }
    Path.pop_back();
}

int KthAnc(int u, int k) {
    if (k > Deep[u]) return 0;
    if (k == 0) return u;
    u = Anc[u][highbit[k]];
    k -= (1 << highbit[k]);
    if (Deep[u] - k == Deep[Top[u]]) return Top[u];
    if (Deep[u] - k > Deep[Top[u]]) return Down[Top[u]][Deep[u] - k - Deep[Top[u]]];
    return Up[Top[u]][Deep[Top[u]] - (Deep[u] - k)];
}

int main() {
    Read(N);
    for (int i = 1;i <= N - 1;++i) {
        int u, v;
        Read(u);Read(v);
        G.add_edge(u, v);
        G.add_edge(v, u);
    }
    DFS1(1, 0);
    DFS2(1, 0, 1);
    int Max = 1;
    for (int i = 1;i <= N;++i) {
        if ((i >> Max) & 1) ++Max;
        highbit[i] = Max - 1;
    }
    Read(M);
    int lastans = 0;
    while (M--) {
        int u, k;
        Read(u);Read(k);
        u ^= lastans;k ^= lastans;
        lastans = KthAnc(u, k);
        printf("%d\n", lastans);
    }

    return 0;
}