30077 - 【模板】树上k级祖先

本题仅作为长链剖分求树上 k 级祖先评测用，不保证卡掉了其他复杂度不正确的做法。

题目描述

给定一棵 n 个点的有根树。

有 q 次询问，第 i 次询问给定 x_i, k_i，要求点 x_i 的 k_i 级祖先，答案为 ans_i。特别地，ans_0 = 0。

本题中的询问将在程序内生成。

给定一个随机种子 s 和一个随机函数 \operatorname{get}(x)：

#define ui unsigned int
ui s;

inline ui get(ui x) {
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return s = x;
}

第一行三个整数 n, q, s。

第二行 n 个整数 f_{1\dots n}，其中 f_i 表示 i 的父亲。特别地，若 f_i = 0，则 i 为根。

一行一个整数，表示 \operatorname{xor}_{i=1}^q i \times ans_i。

样例解释

x_1 = 4，k_1 = 1，ans_1 = 2；
x_2 = 6，k_2 = 3，ans_2 = 5；
x_3 = 3，k_3 = 0，ans_3 = 3；
故输出 1。

数据范围

对于 20\% 的数据，n,q \le 10^3。

对于 50\% 的数据，n,q \le 10^5。

对于 100\% 的数据，2 \le n \le 5 \times 10^5，1 \le q \le 5 \times 10^6，1 \le s < 2^{32}。