Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- const int logn = 18;
- int parent[maxn][logn];
- vector<int> depth(maxn, 0);
- int kth_ancestor(int node, int k) {
- if(depth[node] < k) {
- return -1;
- }
- for(int i = logn; i >= 0; i--) {
- if(node == -1) {
- break;
- }
- if(k & (1 << i)) {
- node = parent[node][i];
- }
- }
- return node;
- }
- int main() {
- int n, q;
- cin >> n >> q;
- vector<int> tree(n + 1, -1);
- for(int i = 2; i <= n; i++) {
- cin >> tree[i];
- parent[i][0] = tree[i];
- }
- tree[1] = 1;
- for(int i = 1; i <= n; i++) {
- if(i != 1) {
- depth[i] = depth[tree[i]] + 1;
- }
- parent[i][0] = tree[i];
- for(int j = 1; j <= logn; j++) {
- parent[i][j] = parent[parent[i][j - 1]][j - 1];
- }
- }
- while(q--) {
- int node, k;
- cin >> node >> k;
- cout << kth_ancestor(node, k) << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement