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 = 5e5 + 5; 
  12. const int Q = 5e5 + 5; 
  13.  
  14. int n, q;  
  15. vector<int> adj[N]; 
  16. string s; 
  17. int c[N]; 
  18.  
  19. int tin[N], tout[N], timer;  
  20. int depth[N]; // depth[u] = Độ sâu của đỉnh u 
  21.  
  22. void dfs(int u, int p) {
  23. 	tin[u] = ++timer;  
  24. 	for (int v : adj[u]) {
  25. 		if (v == p) continue;  
  26. 		depth[v] = depth[u] + 1; 
  27. 		dfs(v, u);  
  28. 	}
  29. 	tout[u] = timer; 
  30. }
  31.  
  32. struct Fenwick {
  33. 	int n;  
  34. 	vector<int> ft;   
  35.  
  36. 	Fenwick(int n) : n(n) {
  37. 		ft.resize(n, 0); 
  38. 	}
  39.  
  40. 	void update(int pos, int val) {
  41. 		for (; pos < n; pos += pos & (-pos)) {
  42. 			ft[pos] ^= val; 
  43. 		}
  44. 	}
  45.  
  46. 	int get(int pos) {
  47. 		int ans = 0; 
  48. 		for (; pos > 0; pos -= pos & (-pos)) {
  49. 			ans ^= ft[pos]; 
  50. 		}
  51. 		return ans;  
  52. 	}
  53. }; 
  54.  
  55. // - Bài toán con: Cho xâu s chỉ chứa các chữ cái in thường, 
  56. //		 	       hỏi có tồn tại cách sắp xếp lại các kí tự trong xâu s sao cho s trở thành xâu đối xứng (palindrome)?
  57. // - Đáp án: (Số lượng kí tự có số lần xuất hiện là lẻ) phải <= 1
  58.  
  59. // - Cây con gốc u sẽ tương ứng với đoạn [tin(u), tout(u)] trên Euler Tour
  60. // - Biến đổi truy vấn trong bài thành: Xét các kí tự của những đỉnh v có trong đoạn [tin(u), tout(u)] và depth[v] = d,
  61. //   hỏi có tồn tại cách sắp xếp lại các kí tự đó sao cho tạo thành xâu đối xứng 
  62.  
  63. // => Có thể sử dụng hướng giải tương tự như ở bài Count Descendants:
  64. //    Chuẩn bị trước các vector pos[d][c] cho từng độ sâu d và kí tự c  
  65. //    Độ phức tạp: O(q * 26 * log2(n)), nhưng với giới hạn của bài này thì vẫn cần tối ưu thêm 
  66.  
  67. // - Nhận xét: Số lượng kí tự là khá ít, chỉ có 26 kí tự ('a' - 'z'), nếu đổi sang số thì sẽ là từ 0 - 25
  68. // => Ta có thể xem mỗi giá trị c ứng với một mask 2^c (chỉ có bit c bật và các bit còn lại đều tắt)
  69. //    Khi đó giá trị mask tương ứng với 1 đoạn sẽ là tổng XOR của đoạn đó 
  70. //	  (tức các giá trị c xuất hiện lẻ lần trong đoạn thì các bit tương ứng sẽ được bật, ngược lại sẽ tắt)
  71. // - Ngoài ra còn có cách xử lí offline bằng Fenwick Tree/Segment Tree: trả lời các truy vấn theo độ cao, đi kèm với nhận xét tối ưu ở trên
  72. //   (Được sử dụng trong code này)
  73. //   Độ phức tạp: O((n + q) * log2(n))
  74.  
  75. vector<int> vertices[N]; // vertices[d] = Danh sách các đỉnh u nằm ở độ sâu d 
  76. vector<ii> queries[N]; 
  77. int ans[Q]; // ans[i] = Đáp án của truy vấn thứ i 
  78.  
  79. int main() {
  80. 	ios::sync_with_stdio(false); 
  81. 	cin.tie(nullptr); 	
  82. 	cin >> n >> q; 
  83. 	for (int u = 2; u <= n; u++) {
  84. 		int p; cin >> p; 
  85. 		adj[u].push_back(p); 
  86. 		adj[p].push_back(u); 
  87. 	}
  88. 	cin >> s; 
  89. 	s = ' ' + s;  
  90. 	for (int u = 1; u <= n; u++) {
  91. 		c[u] = s[u] - 'a'; 
  92. 	}
  93.  
  94. 	timer = 0;  
  95. 	depth[1] = 1;  
  96. 	dfs(1, -1); 
  97.  
  98. 	for (int u = 1; u <= n; u++) {
  99. 		vertices[depth[u]].push_back(u); 
  100. 	}
  101.  
  102. 	for (int i = 0; i < q; i++) {
  103. 		int u, d;  
  104. 		cin >> u >> d; 
  105. 		queries[d].push_back({u, i}); 
  106. 	}
  107.  
  108. 	Fenwick fenw(n + 1); 
  109. 	for (int d = 1; d <= n; d++) {
  110. 		for (int u : vertices[d]) {
  111. 			fenw.update(tin[u], 1 << c[u]); 
  112. 		} 
  113.  
  114. 		for (ii q : queries[d]) {
  115. 			int u = q.first, idx = q.second;  
  116. 			int mask = fenw.get(tout[u]) ^ fenw.get(tin[u] - 1); 
  117. 			ans[idx] = (__builtin_popcount(mask) <= 1); 
  118. 		}
  119.  
  120. 		for (int u : vertices[d]) {
  121. 			fenw.update(tin[u], 1 << c[u]); 
  122. 		}
  123. 	}
  124.  
  125. 	for (int i = 0; i < q; i++) {
  126. 		cout << (ans[i] ? "Yes" : "No") << '\n'; 
  127. 	}
  128. }
Success #stdin #stdout 0.01s 47260KB
comments (?)
stdin
copy 
6 5
1 1 1 3 3
zacccd
1 1
3 3
4 1
6 1
1 2
stdout
copy 
Yes
No
Yes
Yes
Yes
https://ideone.com/Ksbpnk
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!