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.  
  13. // Sử dụng Euler Tour cho Truy vấn Cây con 
  14.  
  15. // Bài này ta cần quan tâm một số truy vấn:
  16. // 1. Gán các đỉnh trong cây con gốc u bằng 1
  17. // 2. Gán các đỉnh trên đường đi từ u đến gốc bằng 0
  18. // 3. In ra giá trị của nút u hiện tại
  19. // Ban đầu các nút đều có giá trị = 0 
  20.  
  21. // - Để trả lời được truy vấn loại 3 thì ta cần xác định truy vấn gần nhất tác động lên u là thuộc loại 1 hay loại 2
  22. // - Gọi latest_type1, latest_type2 lần lượt là chỉ số của truy vấn loại 1, loại 2 gần nhất tác động lên u
  23. //   nếu không tồn tại thì latest_type1/latest_type2 = -1
  24. // => Nếu latest_type1 > latest_type2 thì giá trị của nút u = 1, ngược lại = 0
  25.  
  26. // - Để tính latest_type1 và latest_type2 thì ta dùng 2 cây Segment Tree để quản lí mỗi loại truy vấn
  27. // - Đối với truy vấn loại 1 là Update Cây con và Truy vấn 1 đỉnh thì đã quá quen thuộc
  28. // - Riêng đối với truy vấn loại 2 là Update Đường đi và Truy vấn 1 đỉnh thì ta sẽ áp dụng kiến thức liên quan đến prefix sum
  29. // - Với mỗi cây con gốc u ta sẽ cho tương ứng với đoạn [tin(u), tout(u)] trên Euler Tour
  30. // - Do đó khi ta thay đổi giá trị của 1 đỉnh v nào đấy thì giá trị của những đỉnh là tổ tiên của v, hay nói cách khác là những đỉnh nằm trên đường đi từ v đến gốc cũng sẽ bị thay đổi theo.
  31. // - Nên khi update đường đi từ v đến gốc thì đơn giản là ta chỉ cần update tin(v)
  32. // - Còn khi get giá trị của v thì ta get trong đoạn [tin(v), tout(v)]
  33.  
  34. int n, q;
  35. vector<int> adj[N]; 
  36.  
  37. int tin[N], tout[N], timer; 
  38.  
  39. void dfs(int u, int p) {
  40. 	tin[u] = ++timer; 
  41. 	for (int v : adj[u]) {
  42. 		if (v == p) continue; 
  43. 		dfs(v, u); 
  44. 	}
  45. 	tout[u] = timer; 
  46. }
  47.  
  48. struct SegTree {
  49. 	int n;  
  50. 	vector<int> seg;  
  51. 	vector<int> lazy; 
  52.  
  53. 	SegTree(int n) : n(4 * n) {
  54. 		seg.resize(4 * n, -1);  
  55. 		lazy.resize(4 * n, -1);  
  56. 	}
  57.  
  58. 	void push(int id) {
  59. 		if (lazy[id] != -1) {
  60. 			seg[id * 2] = lazy[id * 2] = lazy[id]; 
  61. 			seg[id * 2 + 1] = lazy[id * 2 + 1] = lazy[id];  
  62. 			lazy[id] = -1;  
  63. 		}
  64. 	}
  65.  
  66. 	void update(int id, int l, int r, int u, int v, int val) {
  67. 		if (l > v || r < u) return; 
  68. 		if (u <= l && r <= v) {
  69. 			seg[id] = val;  
  70. 			lazy[id] = val; 
  71. 			return; 
  72. 		}
  73. 		push(id);  
  74. 		int mid = (l + r) >> 1;  
  75. 		update(id * 2, l, mid, u, v, val); 
  76. 		update(id * 2 + 1, mid + 1, r, u, v, val); 
  77. 		seg[id] = max(seg[id * 2], seg[id * 2 + 1]); 
  78. 	}
  79.  
  80. 	int get(int id, int l, int r, int u, int v) {
  81. 		if (l > v || r < u) return -1;   
  82. 		if (u <= l && r <= v) return seg[id]; 
  83. 		push(id); 
  84. 		int mid = (l + r) >> 1; 
  85. 		return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); 
  86. 	}
  87. }; 
  88.  
  89. int main() {
  90. 	ios::sync_with_stdio(false); 
  91. 	cin.tie(nullptr); 	
  92. 	cin >> n; 
  93. 	for (int i = 0; i < n - 1; i++) {
  94. 		int u, v; 
  95. 		cin >> u >> v; 
  96. 		adj[u].push_back(v); 
  97. 		adj[v].push_back(u); 
  98. 	}
  99.  
  100. 	timer = 0;  
  101. 	dfs(1, -1); 
  102.  
  103. 	cin >> q; 
  104. 	SegTree segtree1(n + 1), segtree2(n + 1); 
  105. 	for (int i = 0; i < q; i++) {
  106. 		int type, u; 
  107. 		cin >> type >> u; 
  108.  
  109. 		if (type == 1) {
  110. 			segtree1.update(1, 1, n, tin[u], tout[u], i);  
  111. 		}
  112. 		else if (type == 2) {
  113. 			segtree2.update(1, 1, n, tin[u], tin[u], i); 
  114. 		}
  115. 		else {
  116. 			int latest_type1 = segtree1.get(1, 1, n, tin[u], tin[u]);  
  117. 			int latest_type2 = segtree2.get(1, 1, n, tin[u], tout[u]);
  118. 			cout << ((latest_type1 > latest_type2) ? 1 : 0) << '\n'; 
  119. 		}
  120. 	}
  121. }
Success #stdin #stdout 0.01s 19124KB
comments (?)
stdin
copy 
5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5
stdout
copy 
0
0
0
1
0
1
0
1
https://ideone.com/udNn0X
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!