fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int MAXN = 100000;
  6. const int LOG  = 18;  // 2^17 = 131072 > 1e5
  7.  
  8. int n, Q;
  9. int parent[MAXN+1];
  10. vector<int> adj[MAXN+1];
  11. int up[LOG][MAXN+1];
  12. int depth[MAXN+1];
  13. int tin[MAXN+1], tout[MAXN+1], timer=0;
  14. vector<int> byDepth[MAXN+1];
  15.  
  16. // 1) DFS to flatten each tree, record tin/tout and depth
  17. void dfs(int u, int p){
  18.     tin[u] = ++timer;
  19.     byDepth[ depth[u] ].push_back(tin[u]);
  20.     up[0][u] = p;
  21.     for(int v: adj[u]){
  22.         if(v==p) continue;
  23.         depth[v] = depth[u] + 1;
  24.         dfs(v, u);
  25.     }
  26.     tout[u] = timer;
  27. }
  28.  
  29. // 2) Jump v up by k steps using binary lifting
  30. int jump(int v, int k){
  31.     for(int j=0; j<LOG && v; j++){
  32.         if(k & (1<<j)) v = up[j][v];
  33.     }
  34.     return v;
  35. }
  36.  
  37. // 3) Count how many values in sorted vector A lie in [L..R]
  38. int countRange(const vector<int>& A, int L, int R){
  39.     auto itL = lower_bound(A.begin(), A.end(), L);
  40.     auto itR = upper_bound(A.begin(), A.end(), R);
  41.     return int(itR - itL);
  42. }
  43.  
  44. int main(){
  45.     ios::sync_with_stdio(false);
  46.     cin.tie(nullptr);
  47.  
  48.     cin >> n;
  49.     // read parent pointers, build forest
  50.     for(int i=1;i<=n;i++){
  51.         int p; 
  52.         cin >> p;
  53.         parent[i] = p;
  54.         if(p!=0){
  55.             adj[i].push_back(p);
  56.             adj[p].push_back(i);
  57.         }
  58.     }
  59.  
  60.     // pick up[0] will be filled in dfs
  61.     // run DFS from each root
  62.     for(int i=1;i<=n;i++){
  63.         if(parent[i]==0){
  64.             depth[i]=0;
  65.             dfs(i, 0);
  66.         }
  67.     }
  68.  
  69.     // build binary‐lifting table
  70.     for(int j=1;j<LOG;j++){
  71.         for(int v=1;v<=n;v++){
  72.             int w = up[j-1][v];
  73.             up[j][v] = w? up[j-1][w] : 0;
  74.         }
  75.     }
  76.  
  77.     // sort each depth list
  78.     int maxDepth = 0;
  79.     for(int i=1;i<=n;i++) 
  80.         if(!byDepth[i].empty()) 
  81.             maxDepth = i;
  82.     for(int d=0; d<=maxDepth; d++){
  83.         sort(byDepth[d].begin(), byDepth[d].end());
  84.     }
  85.  
  86.     // answer queries
  87.     cin >> Q;
  88.     while(Q--){
  89.         int v, p;
  90.         cin >> v >> p;
  91.         // if v has <p ancestors, none
  92.         if(depth[v] < p){
  93.             cout << 0 << " ";
  94.             continue;
  95.         }
  96.         // find p-th ancestor
  97.         int u = jump(v, p);
  98.         // count how many at depth[v] lie in subtree of u
  99.         int d = depth[v];
  100.         int L = tin[u], R = tout[u];
  101.         int total = countRange(byDepth[d], L, R);
  102.         // exclude v itself
  103.         cout << (total - 1) << " ";
  104.     }
  105.     cout << "\n";
  106.     return 0;
  107. }
  108.  
Success #stdin #stdout 0.01s 16420KB
comments (?)
stdin
copy 
6
0 1 1 0 4 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1
stdout
copy 
0 0 1 0 0 1 1
https://ideone.com/y3Fo09
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!