分析

这题太糟糕了，对空间的要求简直变态。上面是题外话。考虑如何求出我的兄弟们，因为兄弟和我是在同一个子树中的，所以在一个相同深度的查询，那么这个一定是一个区间。那么现在就是求一个区间的静态第 小问题。这个可以主席树维护一下。现在的做法，对每个深度开一个主席树，然后二分出来我们要查询的区间。时间复杂度为 。

代码

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
const int N = 1e6 + 1;
vector<int> G[N],S[N];
int fa[N][20],dep[N],si[N],val[N],id[N],Id,n,lastans = 0;
int sum[N*22],lc[N*22],rc[N*22],rt[N],size,cnt,pos[N],A[N];
void dfs(int x,int Fa,int Dep) {
    id[x] = ++Id;A[Id] = x;fa[x][0] = Fa;
    dep[x] = Dep;si[x] = 1;
    S[dep[x]].push_back(id[x]);
    for(auto y:G[x]) {
        if(y == Fa) continue;dfs(y,x,Dep+1);
        si[x] += si[y];
    }
}
int Ask(int x,int k) {
    for(int i = 19;~i;i--) if((k>>i)&1) x = fa[x][i];
    return x;
}
void update(int &a,int b,int l,int r,int pos) {
    a = ++size;
    lc[a] = lc[b];rc[a] = rc[b];sum[a] = sum[b] + 1;
    if(l == r) return;
    int mid = l + r >> 1;
    if(pos <= mid) update(lc[a],lc[b],l,mid,pos);
    else update(rc[a],rc[b],mid+1,r,pos);
}
int Query(int a,int b,int l,int r,int k) {
    if(l == r) return l;
    int d = sum[lc[b]] - sum[lc[a]],mid = l + r >> 1;
    if(d >= k) return Query(lc[a],lc[b],l,mid,k);
    else return Query(rc[a],rc[b],mid+1,r,k-d);
}
int main()
{
    n = read();int Q = read();
    for(int i = 1;i <= n;i++) val[i] = read();
    for(int i = 1;i < n;i++) {
        int a = read(),b = read();
        G[a].push_back(b);G[b].push_back(a);
    }
    dfs(1,0,1);
    for(int j = 1;j <= 19;j++){
        for(int i = 1;i <= n;i++) {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
    for(int i = 1;i <= n;i++) {
        for(auto x:S[i]) {
            pos[x] = ++cnt;
            update(rt[cnt],rt[cnt-1],1,n,val[A[x]]);
        }
    }
    while(Q--) {
        int a = (read() ^ lastans) % n + 1,k = read();
        int Fa = Ask(a,k),l,r;
        if(Fa == 0) {printf("?\n");continue;}
        l = lower_bound(S[dep[a]].begin(),S[dep[a]].end(),id[Fa]) - S[dep[a]].begin();
        r = upper_bound(S[dep[a]].begin(),S[dep[a]].end(),id[Fa]+si[Fa]-1) - S[dep[a]].begin() - 1;
        if(r - l + 1 < k) {printf("?\n");continue;}
        l = S[dep[a]][l];r = S[dep[a]][r];
        lastans = Query(rt[pos[l]-1],rt[pos[r]],1,n,k);
        printf("%d\n",lastans);
    }
    return 0;
}