Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct LinearBinups {
- vector<int> depth;
- vector<int> parent;
- vector<int> jump;
- LinearBinups(int n, int root = 0) {
- depth.resize(n);
- parent.resize(n);
- jump.resize(n);
- parent[root] = jump[root] = root;
- }
- void add_leaf(int v, int par) {
- parent[v] = par;
- depth[v] = depth[par] + 1;
- if (depth[par] - depth[jump[par]] == depth[jump[par]] - depth[jump[jump[par]]]) {
- jump[v] = jump[jump[par]];
- } else {
- jump[v] = par;
- }
- }
- int find_la(int v, int k) {
- int h = max(depth[v] - k, 0);
- while (depth[v] != h) {
- if (depth[jump[v]] >= h) {
- v = jump[v];
- } else {
- v = parent[v];
- }
- }
- return v;
- }
- };
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- int n;
- cin >> n;
- LinearBinups linear_binups(n);
- for (int i = 1; i < n; i++) {
- int par;
- cin >> par; // par < i
- linear_binups.add_leaf(i, par - 1);
- }
- int q;
- cin >> q;
- for (int i = 0; i < q; i++) {
- int v, k;
- cin >> v >> k;
- cout << linear_binups.find_la(v - 1, k) + 1 << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement