Algorithm
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int const N = 2e5 + 1;
bool vis[N];
int n, q, idx[N], siz[N];
vector<int> ord;
vector<vector<int> > g;
int DFS(int u) {
vis[u] = true;
idx[u + 1] = ord.size();
ord.push_back(u + 1);
int ret = 1;
for(int i = 0; i < g[u].size(); ++i)
if(!vis[g[u][i]])
ret += DFS(g[u][i]);
return siz[u + 1] = ret;
}
int main() {
scanf("%d %d", &n, &q);
g.resize(n);
for(int i = 1, a; i < n; ++i) {
scanf("%d", &a);
--a;
g[a].push_back(i);
}
for(int i = 0; i < n; ++i)
sort(g[i].begin(), g[i].end());
DFS(0);
while(q-- != 0) {
int u, k;
scanf("%d %d", &u, &k);
if(idx[u] + siz[u] < idx[u] + k)
puts("-1");
else
printf("%d\n", ord[idx[u] + k - 1]);
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
9 6
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9
1 1 1 3 5 3 5 7
3 1
1 5
3 4
7 3
1 8
1 9
Output
3
6
8
-1
9
4
6
8
-1
9
4
Demonstration
Codeforces Solution-E. Military Problem-Solution in C, C++, Java, Python,Military Problem,Codeforces Solution