Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- typedef long long ll;
- vector<int> k;
- vector<vector<int> > v;
- void dfs(int x,int pr)
- {
- k.push_back(x);
- for(int i=0;i<v[x].size();i++)
- if(pr!=v[x][i])
- dfs(v[x][i],x);
- }
- vector<int> dp(200001,0);
- void dfs1(int x,int pr)
- {
- for(int i=0;i<v[x].size();i++)
- {
- if(pr!=v[x][i])
- {
- dfs1(v[x][i],x);
- dp[x]+=dp[v[x][i]];
- }
- }
- dp[x]++;
- }
- int main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie();
- cout.tie();
- int n;
- cin>>n;
- int q;
- cin>>q;
- vector<int> vec;
- v.insert(v.begin(),200001,vec);
- for(int i=1;i<n;i++)
- {
- int a;
- cin>>a;
- a--;
- v[a].push_back(i);
- }
- for(int i=0;i<n;i++)
- sort(v[i].begin(),v[i].end());
- dfs(0,-1);
- dfs1(0,-1);
- vector<int> ni(200001,0);
- for(int i=0;i<n;i++)
- {
- ni[k[i]]=i;
- }
- for(int i=0;i<q;i++)
- {
- int a;
- cin>>a;
- int b;
- cin>>b;
- a--;
- if(b<=dp[a])
- {
- cout<<k[ni[a]+b-1]+1<<endl;
- }
- else
- cout<<-1<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement