This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#include "../../code/graphs/LCA.cc"
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, q; cin >> n >> q;
vvi adj(n);
FOR (i, 1, n) {
int u; cin >> u;
adj[i].pb(u);
adj[u].pb(i);
}
LCA lca(adj);
while(q--) {
int u, v; cin >> u >> v;
cout << lca.query(u, v) << endl;
}
}
#line 1 "tests/yosupo/sparse_table.lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#line 1 "code/template.cc"
// this line is here for a reason
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define endl '\n'
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define FOR(a, b, c) for (auto a = (b); (a) < (c); ++(a))
#define F0R(a, b) FOR (a, 0, (b))
template <typename T>
bool ckmin(T& a, const T& b) { return a > b ? a = b, true : false; }
template <typename T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, true : false; }
#ifndef DEBUG
#define DEBUG 0
#endif
#define dout if (DEBUG) cerr
#define dvar(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#line 2 "code/dataStructures/SPT.cc"
template <typename T, typename F>
struct SPT {
vector<vector<T>> d;
F f;
SPT (int n, F _f) : d(32 - __builtin_clz(n), vector<T>(n)), f{_f} {}
SPT (const vector<T>& v, F _f) : SPT(SZ(v), _f) {
d[0] = v;
build();
}
void build() {
for (int j = 1; (1 << j) <= SZ(d[0]); ++j) {
for (int i = 0; i + (1 << j) <= SZ(d[0]); ++i) {
d[j][i] = f(d[j - 1][i], d[j - 1][i + (1 << (j - 1))]);
}
}
}
T query(int l, int r) { // [l, r)
int k = 31 - __builtin_clz(r - l);
return f(d[k][l], d[k][r - (1 << k)]);
}
};
#line 2 "code/graphs/LCA.cc"
struct LCA {
vi height, first;
SPT<int, function<int(int, int)>> spt;
LCA(vvi& adj, int root = 0) : height(SZ(adj), -1), first(SZ(adj), -1),
spt(2 * SZ(adj) - 1, [self = this](int a, int b) {
return self->height[a] < self->height[b] ? a : b;
}) {
int idx = 0;
dfs(adj, root, idx);
spt.build();
}
void dfs(vvi& adj, int v, int& idx, int h = 0) {
first[v] = idx;
spt.d[0][idx++] = v;
height[v] = h;
for (int u : adj[v]) if (first[u] == -1) {
dfs(adj, u, idx, h + 1);
spt.d[0][idx++] = v;
}
}
int query(int a, int b) {
ii m = minmax(first[a], first[b]);
return spt.query(m.fi, m.se);
}
};
#line 4 "tests/yosupo/sparse_table.lca.test.cpp"
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n, q; cin >> n >> q;
vvi adj(n);
FOR (i, 1, n) {
int u; cin >> u;
adj[i].pb(u);
adj[u].pb(i);
}
LCA lca(adj);
while(q--) {
int u, v; cin >> u >> v;
cout << lca.query(u, v) << endl;
}
}