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; 
  14. int c[N]; 
  15. vector<int> adj[N]; 
  16.  
  17. void compress(int c[]) {
  18. 	vector<int> vals;  
  19. 	for (int i = 1; i <= n; i++) vals.push_back(c[i]);  
  20. 	sort(vals.begin(), vals.end());  
  21. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());  
  22. 	for (int i = 1; i <= n; i++) {
  23. 		c[i] = lower_bound(vals.begin(), vals.end(), c[i]) - vals.begin(); 
  24. 	}
  25. }
  26.  
  27. int euler_tour[N];  
  28. int tin[N], tout[N], timer;   
  29.  
  30. void dfs(int u, int p) {
  31. 	tin[u] = ++timer;  
  32. 	euler_tour[timer] = u;  
  33. 	for (int v : adj[u]) {
  34. 		if (v == p) continue;  
  35. 		dfs(v, u); 
  36. 	}
  37. 	tout[u] = timer; 
  38. }
  39.  
  40. // - Cây con gốc u sẽ tương ứng với đoạn [tin(u), tout(u)] trên Euler Tour 
  41. // => Đưa về bài toán đếm số phần tử phân biệt nằm trong đoạn (Tham khảo sol của anh bài D-query)
  42.  
  43. struct Fenwick {
  44. 	int n;  
  45. 	vector<int> ft; 
  46.  
  47. 	Fenwick(int n) : n(n) {
  48. 		ft.resize(n, 0); 
  49. 	}
  50.  
  51. 	void update(int pos, int val) {
  52. 		for (; pos < n; pos += pos & (-pos)) {
  53. 			ft[pos] += val; 
  54. 		}
  55. 	}
  56.  
  57. 	int get(int pos) {
  58. 		int ans = 0;  
  59. 		for (; pos > 0; pos -= pos & (-pos)) {
  60. 			ans += ft[pos];
  61. 		}
  62. 		return ans; 
  63. 	}
  64. }; 
  65.  
  66. vector<int> queries[N]; // queries[R] = danh sách những truy vấn có đầu mút r = R
  67. int last[N]; // last[x] = i gần nhất sao cho c[i] == x
  68. int pre[N]; // pre[i] = j gần nhất sao cho c[j] == c[i]
  69. int ans[N]; // ans[u] = Đáp án của cây con gốc u 
  70.  
  71. int main() {
  72. 	ios::sync_with_stdio(false); 
  73. 	cin.tie(nullptr); 	
  74. 	cin >> n; 
  75. 	for (int u = 1; u <= n; u++) {
  76. 		cin >> c[u]; 
  77. 	}
  78. 	compress(c);   
  79.  
  80. 	for (int i = 0; i < n - 1; i++) {
  81. 		int u, v; 
  82. 		cin >> u >> v; 
  83. 		adj[u].push_back(v); 
  84. 		adj[v].push_back(u); 
  85. 	}
  86.  
  87. 	timer = 0;  
  88. 	dfs(1, -1); 
  89.  
  90. 	for (int u = 1; u <= n; u++) {
  91. 		queries[tout[u]].push_back(u); 
  92. 	}
  93.  
  94. 	for (int i = 1; i <= n; i++) {
  95. 		int u = euler_tour[i]; 
  96. 		pre[i] = last[c[u]]; 
  97. 		last[c[u]] = i;  
  98. 	}
  99.  
  100. 	Fenwick fenw(n + 1); 
  101. 	for (int r = 1; r <= n; r++) {
  102. 		if (pre[r] > 0) fenw.update(pre[r], -1);  
  103. 		fenw.update(r, 1); 
  104. 		for (int u : queries[r]) {
  105. 			ans[u] = fenw.get(r) - fenw.get(tin[u] - 1); 
  106. 		}
  107. 	}
  108.  
  109. 	for (int u = 1; u <= n; u++) {
  110. 		cout << ans[u] << ' '; 
  111. 	}
  112. }
Success #stdin #stdout 0.01s 16932KB
comments (?)
stdin
copy 
5
2 3 2 2 1
1 2
1 3
3 4
3 5
stdout
copy 
3 1 2 1 1
https://ideone.com/iRCPjl
language:
C++14 (gcc 8.3)
created:
179 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!