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. // - Ta cần giải quyết 2 bài toán lớn trong bài này: 
  12. // 1. Tính lca(u, v) với root bất kì
  13. // 2. Update/Get giá trị của một cây con gốc u với root bất kì
  14. // - Ở cả 2 bài toán thì ta đều sẽ chọn cây với gốc là 1 (lca, tin, tout)
  15. // - Bài toán 1 thì các em tham khảo sol bài dynamic LCA
  16. // - Với Bài toán 2 thì thật ra chỉ đòi hỏi khả năng casework (xét trường hợp) chứ không hề khó:
  17. // TH1: u = root: 
  18. // -> Update/Get cả cây
  19. // TH2: u != root: 
  20. // 2.1: u và root có quan hệ tổ tiên:
  21. // a) root là tổ tiên của u:
  22. // -> Update/Get cây con gốc u
  23. // b) u là tổ tiên của root:
  24. // -> Gọi v là đỉnh con của u mà là tổ tiên của root
  25. // -> Update/Get các đỉnh nằm ngoài cây con gốc v
  26. // 2.2: u và root không có quan hệ tổ tiên (nằm khác nhánh)
  27. // -> Update/Get cây con gốc u 
  28.  
  29. const int N = 1e5 + 5; 
  30. const int LOG = 17;  
  31.  
  32. int n, q; 
  33. int a[N]; 
  34. vector<int> adj[N]; 
  35.  
  36. int up[LOG][N]; 
  37. int tin[N], tout[N], timer; 
  38.  
  39. void dfs(int u, int p) {
  40. 	tin[u] = ++timer; 
  41. 	up[0][u] = p;  
  42. 	for (int i = 1; i < LOG; i++) {
  43. 		up[i][u] = up[i - 1][up[i - 1][u]];
  44. 	}
  45. 	for (int v : adj[u]) {
  46. 		if (v == p) continue; 
  47. 		dfs(v, u); 
  48. 	}
  49. 	tout[u] = timer; 
  50. }
  51.  
  52. bool isAncestor(int u, int v) {
  53. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  54. }
  55.  
  56. int nextOnPath(int u, int v) {
  57. 	for (int i = LOG - 1; i >= 0; i--) {
  58. 		if (!isAncestor(up[i][v], u)) {
  59. 			v = up[i][v]; 
  60. 		}
  61. 	}
  62. 	return v; 
  63. }
  64.  
  65. int lca(int u, int v) {
  66. 	if (isAncestor(u, v)) return u; 
  67. 	if (isAncestor(v, u)) return v; 
  68. 	for (int i = LOG - 1; i >= 0; i--) {
  69. 		if (!isAncestor(up[i][u], v)) {
  70. 			u = up[i][u]; 
  71. 		}
  72. 	}
  73. 	return up[0][u];
  74. }
  75.  
  76. struct SegTree {
  77. 	int n;  
  78. 	vector<ll> seg; 
  79. 	vector<ll> lazy;   
  80.  
  81. 	SegTree() {}
  82.  
  83. 	SegTree(int n) : n(n) {
  84. 		seg.resize(4 * n, 0); 
  85. 		lazy.resize(4 * n, 0); 
  86. 	}
  87.  
  88. 	void push(int id, int l, int r) {
  89. 		if (lazy[id]) {
  90. 			int mid = (l + r) >> 1; 
  91. 			seg[id * 2] += (mid - l + 1) * lazy[id]; 
  92. 			lazy[id * 2] += lazy[id]; 
  93. 			seg[id * 2 + 1] += (r - mid) * lazy[id];
  94. 			lazy[id * 2 + 1] += lazy[id]; 
  95. 			lazy[id] = 0;  
  96. 		}
  97. 	}
  98.  
  99. 	void update(int id, int l, int r, int u, int v, int val) {
  100. 		if (l > v || r < u) return; 
  101. 		if (u <= l && r <= v) {
  102. 			seg[id] += 1ll * (r - l + 1) * val; 
  103. 			lazy[id] += val; 
  104. 			return; 
  105. 		}
  106. 		push(id, l, r); 
  107. 		int mid = (l + r) >> 1; 
  108. 		update(id * 2, l, mid, u, v, val); 
  109. 		update(id * 2 + 1, mid + 1, r, u, v, val); 
  110. 		seg[id] = seg[id * 2] + seg[id * 2 + 1]; 
  111. 	}
  112.  
  113. 	ll get(int id, int l, int r, int u, int v) {
  114. 		if (l > v || r < u) return 0;  
  115. 		if (u <= l && r <= v) return seg[id]; 
  116. 		push(id, l, r); 
  117. 		int mid = (l + r) >> 1; 
  118. 		return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v); 
  119. 	}
  120. }; 
  121.  
  122. SegTree segtree;  
  123.  
  124. void updateSubtree(int u, int val, int root) {
  125. 	if (u == root) {
  126. 		segtree.update(1, 1, n, 1, n, val); 
  127. 		return; 
  128. 	}
  129. 	if (isAncestor(root, u)) {
  130. 		segtree.update(1, 1, n, tin[u], tout[u], val); 
  131. 		return; 
  132. 	}
  133. 	if (isAncestor(u, root)) {
  134. 		int v = nextOnPath(u, root);  
  135. 		segtree.update(1, 1, n, 1, n, val); 
  136. 		segtree.update(1, 1, n, tin[v], tout[v], -val); 	
  137. 		return; 	
  138. 	}
  139. 	segtree.update(1, 1, n, tin[u], tout[u], val); 
  140. }
  141.  
  142. ll querySubtree(int u, int root) {
  143. 	if (u == root) {
  144. 		return segtree.seg[1]; 
  145. 	}
  146. 	if (isAncestor(root, u)) {
  147. 		return segtree.get(1, 1, n, tin[u], tout[u]); 
  148. 	}
  149. 	if (isAncestor(u, root)) {
  150. 		int v = nextOnPath(u, root);  
  151. 		return segtree.seg[1] - segtree.get(1, 1, n, tin[v], tout[v]); 
  152. 	}
  153. 	return segtree.get(1, 1, n, tin[u], tout[u]); 
  154. }
  155.  
  156. int main() {
  157. 	ios::sync_with_stdio(false); 
  158. 	cin.tie(nullptr); 	
  159. 	cin >> n >> q;
  160. 	for (int u = 1; u <= n; u++) cin >> a[u]; 
  161.  
  162. 	for (int i = 0; i < n - 1; i++) {
  163. 		int u, v; 
  164. 		cin >> u >> v; 
  165. 		adj[u].push_back(v); 
  166. 		adj[v].push_back(u); 
  167. 	}
  168.  
  169. 	int root = 1;  
  170. 	timer = 0; 
  171. 	dfs(1, 1);   
  172.  
  173. 	segtree = SegTree(n + 1); 
  174. 	for (int u = 1; u <= n; u++) {
  175. 		segtree.update(1, 1, n, tin[u], tin[u], a[u]);  
  176. 	}
  177.  
  178. 	while (q--) {
  179. 		int type; cin >> type; 
  180.  
  181. 		if (type == 1) {
  182. 			int nroot; cin >> nroot; 
  183. 			root = nroot; 
  184. 		}
  185. 		else if (type == 2) {
  186. 			int u, v, val; 
  187. 			cin >> u >> v >> val;  
  188. 			int lca_uv = lca(u, v) ^ lca(u, root) ^ lca(v, root); 
  189. 			updateSubtree(lca_uv, val, root); 
  190. 		}
  191. 		else {
  192. 			int u; cin >> u;  
  193. 			cout << querySubtree(u, root) << '\n'; 
  194. 		}	
  195. 	}
  196. }
  197.  
Success #stdin #stdout 0.01s 12216KB
comments (?)
stdin
copy 
6 7
1 4 2 8 5 7
1 2
3 1
4 3
4 5
3 6
3 1
2 4 6 3
3 4
1 6
2 2 4 -5
1 4
3 3
stdout
copy 
27
19
5
https://ideone.com/gVBY9o
language:
C++14 (gcc 8.3)
created:
173 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!