fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100005;
  5. const int LOG = 20;
  6.  
  7. int n, m;
  8. vector<int> g[N];
  9. int up[N][LOG], depth[N], inT[N], outT[N], timer = 0;
  10. vector<int> depthList[N];
  11.  
  12. void dfs(int v, int p) {
  13.     inT[v] = timer++;
  14.     up[v][0] = p;
  15.     for (int j = 1; j < LOG; j++) {
  16.         if (up[v][j-1]) up[v][j] = up[up[v][j-1]][j-1];
  17.         else up[v][j] = 0;
  18.     }
  19.  
  20.     depthList[depth[v]].push_back(inT[v]);
  21.  
  22.     for (int to : g[v]) {
  23.         depth[to] = depth[v] + 1;
  24.         dfs(to, v);
  25.     }
  26.  
  27.     outT[v] = timer;
  28. }
  29.  
  30. int getAncestor(int v, int k) {
  31.     for (int j = 0; j < LOG; j++) {
  32.         if (k & (1 << j)) {
  33.             v = up[v][j];
  34.             if (!v) return 0; // ancestor doesn't exist
  35.         }
  36.     }
  37.     return v;
  38. }
  39.  
  40. int query(int v, int p) {
  41.     int z = getAncestor(v, p);
  42.     if (!z) return 0; // no such ancestor
  43.  
  44.     auto &vec = depthList[depth[v]];
  45.     // count nodes in subtree of z with same depth
  46.     int L = lower_bound(vec.begin(), vec.end(), inT[z]) - vec.begin();
  47.     int R = lower_bound(vec.begin(), vec.end(), outT[z]) - vec.begin();
  48.     return (R - L - 1); // exclude v itself
  49. }
  50.  
  51. int main() {
  52.     ios::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.  
  55.     cin >> n;
  56.     vector<int> parent(n + 1);
  57.     for (int i = 1; i <= n; i++) {
  58.         cin >> parent[i];
  59.         if (parent[i] != 0) {
  60.             g[parent[i]].push_back(i);
  61.         }
  62.     }
  63.  
  64.     // run DFS from all roots
  65.     for (int i = 1; i <= n; i++) {
  66.         if (parent[i] == 0) {
  67.             depth[i] = 0;
  68.             dfs(i, 0);
  69.         }
  70.     }
  71.  
  72.     // sort depth lists for binary search
  73.     for (int d = 0; d <= n; d++) {
  74.         sort(depthList[d].begin(), depthList[d].end());
  75.     }
  76.  
  77.     cin >> m;
  78.     vector<int> ans(m);
  79.     for (int i = 0; i < m; i++) {
  80.         int v, p;
  81.         cin >> v >> p;
  82.         ans[i] = query(v, p);
  83.     }
  84.  
  85.     for (int i = 0; i < m; i++) {
  86.         cout << ans[i] << " ";
  87.     }
  88.     cout << "\n";
  89.  
  90.     return 0;
  91. }
  92.  
Success #stdin #stdout 0.01s 11112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/diJosU
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
5 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!