Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <vector>
- #include <set>
- #include <map>
- #include <stack>
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- const int logn = 18;
- int parent[maxn];
- int up_node[maxn][logn + 5];
- int depth_of_node[maxn];
- int main() {
- ios_base::sync_with_stdio(false);
- int n, q;
- cin >> n >> q;
- for(int i = 1; i < n; i++) {
- int p;
- cin >> p;
- p--;
- parent[i] = p;
- }
- memset(depth_of_node, 0, sizeof depth_of_node);
- memset(up_node, 0, sizeof up_node);
- parent[0] = 0;
- for(int i = 0; i < n; i++) {
- up_node[i][0] = parent[i];
- if(i != 0) {
- depth_of_node[i] = depth_of_node[parent[i]] + 1;
- }
- for(int j = 1; j <= logn; j++) {
- up_node[i][j] = up_node[ up_node[i][j - 1] ][j - 1];
- }
- }
- while(q--) {
- int node, k;
- cin >> node >> k;
- node--;
- if(depth_of_node[node] < k) {
- cout << -1 << endl;
- continue;
- }
- for(int i = logn; i >= 0; i--) {
- if(node == -1) {
- break;
- }
- if(k & (1 << i)) {
- node = up_node[node][i];
- }
- }
- if(node != -1) {
- node++;
- }
- cout << node << endl;
- }
- return 0;
- }
- // 200000
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement