Advertisement
Guest User

Untitled

a guest
Jul 16th, 2018
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. vector<int> k;
  7. vector<vector<int> > v;
  8. void dfs(int x,int pr)
  9. {
  10. k.push_back(x);
  11. for(int i=0;i<v[x].size();i++)
  12. if(pr!=v[x][i])
  13. dfs(v[x][i],x);
  14. }
  15. vector<int> dp(200001,0);
  16. void dfs1(int x,int pr)
  17. {
  18. for(int i=0;i<v[x].size();i++)
  19. {
  20. if(pr!=v[x][i])
  21. {
  22. dfs1(v[x][i],x);
  23. dp[x]+=dp[v[x][i]];
  24. }
  25. }
  26. dp[x]++;
  27. }
  28. int main()
  29. {
  30. ios_base::sync_with_stdio(false);
  31. cin.tie();
  32. cout.tie();
  33. int n;
  34. cin>>n;
  35. int q;
  36. cin>>q;
  37. vector<int> vec;
  38. v.insert(v.begin(),200001,vec);
  39. for(int i=1;i<n;i++)
  40. {
  41. int a;
  42. cin>>a;
  43. a--;
  44. v[a].push_back(i);
  45. }
  46. for(int i=0;i<n;i++)
  47. sort(v[i].begin(),v[i].end());
  48. dfs(0,-1);
  49. dfs1(0,-1);
  50. vector<int> ni(200001,0);
  51. for(int i=0;i<n;i++)
  52. {
  53. ni[k[i]]=i;
  54. }
  55. for(int i=0;i<q;i++)
  56. {
  57. int a;
  58. cin>>a;
  59. int b;
  60. cin>>b;
  61. a--;
  62. if(b<=dp[a])
  63. {
  64. cout<<k[ni[a]+b-1]+1<<endl;
  65. }
  66. else
  67. cout<<-1<<endl;
  68. }
  69. return 0;
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement