如题

运用长链剖分即可做到预处理$O(n\log n)$询问$O(1)$

根据长链剖分的性质

某个点的$k$级祖先所在的长链长度$\geq k$

则如果我们先跳$h=2^{k二进制最高位}$,$fa[x][k]$所在长链$\geq k >k-h$,要么在所在长链上，要在长链顶端$L\leq len[top[fa[x][k]]]$。

预处理这些所需的即可。

代码

```c++

include

using namespace std;

define ll long long

define ui unsigned int

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 1e9 + 7;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * f;
}

int n, q;
ui s;
vector g[N], u[N], v[N];
int son[N], dep[N], len[N], top[N], f[N][20];

inline ui get(ui x)
{
return x ^= x << 13, x ^= x >> 17, x ^= x << 5, s = x;
}
void dfs1(int x)
{
dep[x] = dep[f[x][0]] + 1;
for (int i = 1; (1 << i) <= n; i++)
f[x][i] = f[f[x][i - 1]][i - 1];
for (int to : g[x])
{
dep[to] = dep[x] + 1;
f[to][0] = x;
dfs1(to);
son[x] = (len[to] > len[son[x]]) ? to : son[x];
}
len[x] = len[son[x]] + 1;
}
void dfs2(int x, int p)
{
top[x] = p;
if (x == p)
{
for (int i = 0, o = x; i < len[x]; o = f[o][0], i++)
u[x].push_back(o);
for (int i = 0, o = x; i < len[x]; o = son[o], i++)
v[x].push_back(o);
}
if (son[x])
dfs2(son[x], p);
for (int to : g[x])
if (son[x] != to)
dfs2(to, to);
}
int h[N];
int query(int x, int k)
{
if (k == 0)
return x;
x = f[x][h[k]];
k -= 1 << h[k];
k -= -dep[top[x]] + dep[x];

if (k > 0)
    return u[top[x]][k];
else
    return v[top[x]][-k];

}
int main()
{

n = read(), q = read(), s = read();
h[0] = -1;
for (int i = 1; i <= n; i++)
{
    int fa = read();
    h[i] = h[i >> 1] + 1;
    g[fa].push_back(i);
}
int rt = g[0][0];
dfs1(rt);
dfs2(rt, rt);
ll ans = 0, res = 0;
for (int i = 1, x, k; i <= q; i++)
{
    x = (get(s) ^ ans) % n + 1;
    k = (get(s) ^ ans) % dep[x];

    res ^= 1ll * i * (ans = query(x, k));
}
cout << res << endl;
return 0;

}