fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 2e5 + 5; 
  12.  
  13. int n, q;  
  14. vector<int> adj[N]; 
  15.  
  16. int tin[N], tout[N], timer;   
  17. int depth[N]; // depth[u] = Độ sâu của đỉnh u
  18.  
  19. void dfs(int u, int p) {
  20. 	tin[u] = ++timer;  
  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. // - Bài toán: Đếm số lượng đỉnh v có trong cây con gốc u sao cho depth[v] = d
  30. // - Cây con gốc u sẽ tương ứng với đoạn [tin(u), tout(u)] trên Euler Tour
  31. // => Biến đổi thành bài toán đếm số lượng phần tử trong đoạn có giá trị = d
  32. // => Bài toán kinh điển của tìm kiếm nhị phân
  33. //    Ngoài ra cũng có cách xử lí offline bằng Fenwick Tree / Segment Tree: trả lời các truy vấn theo độ cao
  34.  
  35. vector<int> pos[N]; // pos[d] = Danh sách vị trí (tin[u]) của các đỉnh ở độ sâu d theo thứ tự tăng dần
  36.  
  37. int main() {
  38. 	ios::sync_with_stdio(false); 
  39. 	cin.tie(nullptr); 	
  40. 	cin >> n; 
  41. 	for (int u = 2; u <= n; u++) {
  42. 		int p; cin >> p;  
  43. 		adj[p].push_back(u); 
  44. 		adj[u].push_back(p); 
  45. 	}
  46.  
  47. 	timer = 0;   
  48. 	depth[1] = 0;  
  49. 	dfs(1, -1);  
  50.  
  51. 	for (int u = 1; u <= n; u++) {
  52. 		pos[depth[u]].push_back(tin[u]); 
  53. 	}
  54. 	for (int d = 0; d <= n - 1; d++) {
  55. 		sort(pos[d].begin(), pos[d].end()); 
  56. 	}
  57.  
  58. 	cin >> q; 
  59. 	while (q--) {
  60. 		int u, d; 
  61. 		cin >> u >> d;  
  62. 		int ans = upper_bound(pos[d].begin(), pos[d].end(), tout[u]) - 
  63. 				  lower_bound(pos[d].begin(), pos[d].end(), tin[u]); 
  64. 		cout << ans << '\n'; 
  65. 	}
  66. }
Success #stdin #stdout 0.01s 15176KB
comments (?)
stdin
copy 
7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5
stdout
copy 
3
1
0
0
https://ideone.com/RqbYMh
language:
C++14 (gcc 8.3)
created:
180 days ago
visibility:
secret

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!