方法 0
直接长链剖分，常数大
时间复杂度 $\Theta\left(n \log n + q\right)$
方法 1
直接倍增
时间复杂度 $\Theta\left(n \log n + q \log n\right)$
方法 2
使用重链剖分，跳到刚好超过 $k$ 级的链的顶端，然后通过 dfs 序推 $k$ 级祖先。
时间复杂度 $\mathcal O\left(n + q \log n\right)$
方法 3
考虑优化方法 2。可以二分刚好超过 $k$ 级的链，这样找这条链的时间复杂度就从 $\mathcal O\left(\log n\right)$ 降至了 $\mathcal O\left(\log \log n\right)$，但是常数较大。
时间复杂度 $\mathcal O\left(n + q \log \log n\right)$
方法 4
考虑优化方法 2。往上跳重链的时候分块跳，每次跳 $\sqrt{\log n}$ 条链。需要预处理每个点的 $\sqrt{\log n}$ 级祖先。常数很小，是我在数据随机的情况下测试的最快的做法。
时间复杂度 $\Theta\left(n \sqrt{\log n} + q \sqrt{\log n}\right)$
代码：
// Please submit with C++17! It's best to use C++20 or higher version.
// By Koicy (https://koicy.ly)
// rbtree (i@koicy.ly)
// This is my kingdom come.
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <tuple>
#include <vector>
#define gex(a, b, func) a = func(a, b)
// #define EFILE ""
using namespace std;
using tp = long long;
template <typename _Type, size_t _Size>
struct mray : array<_Type, _Size + 9> {
_Type& operator[](size_t index) { return this->at(index); }
};
void DEMONS() {
}
// Constants
static constexpr tp Hat_N = 5e5;
// Classes
// Typedeves
// Variables
tp n, m, rt, cnt, las, ans, len;
// Arrays
mray<tp, Hat_N> hson, dep, top, fa, id, toid, up;
mray<vector<tp>, Hat_N> tr;
// Functions
tp dfs1(tp x, tp f) {
tp temp = -1, s = 1;
dep[x] = dep[f] + 1;
for (auto&& i : tr[x]) {
if (i != f) {
tp si = dfs1(i, x);
fa[i] = x;
s += si;
if (temp < si) {
hson[x] = i;
temp = si;
}
}
}
return s;
}
void dfs2(tp x, tp h) {
top[toid[id[x] = ++cnt] = x] = h;
if (hson[x]) dfs2(hson[x], h);
if (x == top[x]) {
up[x] = x;
for (int i = 1; i <= len && top[fa[up[x]]] != 1; ++i) up[x] = top[fa[up[x]]];
} else up[x] = up[top[x]];
for (auto&& i : tr[x]) {
if (i != fa[x] && i != hson[x]) dfs2(i, i);
}
}
tp jump(tp x, tp k) {
while (k >= dep[x] - dep[up[x]] + 1) {
k -= dep[x] - dep[up[x]] + 1;
x = fa[up[x]];
}
while (k >= id[x] - id[top[x]] + 1) {
k -= id[x] - id[top[x]] + 1;
x = fa[top[x]];
}
return toid[id[x] - k];
}
void IMAGINARY([[maybe_unused]] tp TEST_NUMBER) {
cin >> n >> m;
len = sqrt(log2(n));
for (tp i = 1; i <= n; ++i) {
tp f;
cin >> f;
if (!f) rt = i;
else {
tr[i].push_back(f);
tr[f].push_back(i);
}
}
dfs1(rt, rt);
dfs2(rt, rt);
while (m--) {
tp u, v;
cin >> u >> v;
cout << jump(u, v) << ' ';
}
cout << '\n';
}
#include <fstream>
signed main() {
tp t = 0, _t = 1;
ios::sync_with_stdio(0);
cin.tie(0);
#if !_CONSOLE
#ifdef _LOCAL
static ifstream _in("input.in");
cin.rdbuf(_in.rdbuf());
#else
#ifdef EFILE
static ifstream _in(EFILE ".in");
static ofstream _out(EFILE ".out");
cin.rdbuf(_in.rdbuf());
cout.rdbuf(_out.rdbuf());
#endif
#endif
#endif
// cin >> _t;
DEMONS();
while (t < _t) IMAGINARY(++t);
return 0;
}
//*/