fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100000 + 10;
  6.  
  7. struct Node {
  8. 	int cnt, col, lm, rm;
  9. };
  10.  
  11. vector<int> adj[N];
  12. int a[N], dep[N], fa[N], hson[N], sz[N], top[N], dfn[N], ord[N];
  13. Node sgt[N*4];
  14. int n, m, t;
  15.  
  16. void dfs1(int u, int p) {
  17. 	sz[u] = 1;
  18. 	for (int v: adj[u]) {
  19. 		if (v == p) continue;
  20. 		dep[v] = dep[u] + 1;
  21. 		fa[v] = u;
  22. 		dfs1(v, u);
  23. 		sz[u] += sz[v];
  24. 		if (!hson[u] || sz[v] > sz[hson[u]]) hson[u] = v;
  25. 	}
  26. }
  27.  
  28. void dfs2(int u, int p) {
  29. 	dfn[u] = ++ t;
  30. 	ord[t] = u;
  31. 	if (!hson[u]) return;
  32. 	top[hson[u]] = top[u];
  33. 	dfs2(hson[u], u);
  34. 	for (int v: adj[u]) {
  35. 		if (v == p || v == hson[u]) continue;
  36. 		top[v] = v;
  37. 		dfs2(v, u);
  38. 	}
  39. }
  40.  
  41. void push_down(int index, int begin, int end) {
  42. 	if (sgt[index].col) {
  43. 		int mid = (begin + end) / 2;
  44. 		sgt[index*2] = sgt[index*2+1] = {1, sgt[index].col, sgt[index].col, sgt[index].col};
  45. 		sgt[index].col = 0;
  46. 	}
  47. }
  48.  
  49. void push_up(int index) {
  50. 	sgt[index].cnt = sgt[index*2].cnt + sgt[index*2+1].cnt;
  51. 	if (sgt[index*2].rm == sgt[index*2+1].lm) sgt[index].cnt --;
  52. 	sgt[index].lm = sgt[index*2].lm;
  53. 	sgt[index].rm = sgt[index*2+1].rm;
  54. }
  55.  
  56. void build(int index, int begin, int end) {
  57. 	if (begin >= end) {
  58. 		sgt[index] = {1, 0, a[ord[begin]], a[ord[begin]]};
  59. 		return;
  60. 	}
  61. 	int mid = (begin + end) / 2;
  62. 	build(index * 2, begin, mid);
  63. 	build(index * 2 + 1, mid + 1, end);
  64. 	push_up(index);
  65. }
  66.  
  67. void update(int index, int begin, int end, int left, int right, int val) {
  68. 	if (left <= begin && right >= end) {
  69. 		sgt[index] = {1, val, val, val};
  70. 		return;
  71. 	}
  72. 	push_down(index, begin, end);
  73. 	int mid = (begin + end) / 2;
  74. 	if (right <= mid) update(index * 2, begin, mid, left, right, val);
  75. 	else if (left > mid) update(index * 2 + 1, mid + 1, end, left, right, val);
  76. 	else {
  77. 		update(index * 2, begin, mid, left, mid, val);
  78. 		update(index * 2 + 1, mid + 1, end, mid + 1, right, val);
  79. 	}
  80. 	push_up(index);
  81. }
  82.  
  83. Node query(int index, int begin, int end, int left, int right) {
  84. 	if (left <= begin && right >= end) return sgt[index];
  85. 	push_down(index, begin, end);
  86. 	int mid = (begin + end) / 2;
  87. 	if (right <= mid) return query(index * 2, begin, mid, left, right);
  88. 	else if (left > mid) return query(index * 2 + 1, mid + 1, end, left, right);
  89. 	else {
  90. 		Node node1 = query(index * 2, begin, mid, left, mid);
  91. 		Node node2 = query(index * 2 + 1, mid + 1, end, mid + 1, right);
  92. 		int cnt = node1.cnt + node2.cnt;
  93. 		if (node1.rm == node2.lm) cnt --;
  94. 		return (Node){cnt, 0, node1.lm, node2.rm};
  95. 	}
  96. }
  97.  
  98. void update(int u, int v, int c) {
  99. 	int fu = top[u], fv = top[v];
  100. 	while (fu != fv) {
  101. 		if (dep[fu] >= dep[fv]) {
  102. 			update(1, 1, n, dfn[fu], dfn[u], c);
  103. 			u = fa[fu];
  104. 		}
  105. 		else {
  106. 			update(1, 1, n, dfn[fv], dfn[v], c);
  107. 			v = fa[fv];
  108. 		}
  109. 		fu = top[u];
  110. 		fv = top[v];
  111. 	}
  112. 	if (dfn[u] <= dfn[v]) update(1, 1, n, dfn[u], dfn[v], c);
  113. 	else update(1, 1, n, dfn[v], dfn[u], c);
  114. }
  115.  
  116. int query(int u, int v) {
  117. 	int s = 0, fu = top[u], fv = top[v], c1 = -1, c2 = -1;
  118. 	Node node;
  119. 	while (fu != fv) {
  120. 		if (dep[fu] >= dep[fv]) {
  121. 			node = query(1, 1, n, dfn[fu], dfn[u]);
  122. 			s += node.cnt;
  123. 			if (c1 == node.rm) s --;
  124. 			c1 = node.lm;
  125. 			u = fa[fu];
  126. 		}
  127. 		else {
  128. 			node = query(1, 1, n, dfn[fv], dfn[v]);
  129. 			s += node.cnt;
  130. 			if (c2 == node.rm) s --;
  131. 			c2 = node.lm;
  132. 			v = fa[fv];
  133. 		}
  134. 		fu = top[u];
  135. 		fv = top[v];
  136. 	}
  137. 	if (dfn[u] <= dfn[v]) {
  138. 		node = query(1, 1, n, dfn[u], dfn[v]);
  139. 		s += node.cnt;
  140. 		if (c1 == node.lm) s --;
  141. 		if (c2 == node.rm) s --;
  142. 	}
  143. 	else {
  144. 		node = query(1, 1, n, dfn[v], dfn[u]);
  145. 		s += node.cnt;
  146. 		if (c1 == node.rm) s --;
  147. 		if (c2 == node.lm) s --;
  148. 	}
  149. 	return s;
  150. }
  151.  
  152. int main() {
  153. 	int u, v, c;
  154. 	char op;
  155. 	scanf("%d %d", &n, &m);
  156. 	for (int i=1; i<=n; i++) scanf("%d", &a[i]);
  157. 	for (int i=0; i<n-1; i++) {
  158. 		scanf("%d %d", &u, &v);
  159. 		adj[u].push_back(v);
  160. 		adj[v].push_back(u);
  161. 	}
  162. 	dfs1(1, -1);
  163. 	top[1] = fa[1] = 1;
  164. 	dfs2(1, -1);
  165. 	build(1, 1, n);
  166. 	while (m --) {
  167. 		scanf(" %c", &op);
  168. 		if (op == 'C') {
  169. 			scanf("%d %d %d", &u, &v, &c);
  170. 			update(u, v, c);
  171. 		}
  172. 		else {
  173. 			scanf("%d %d", &u, &v);
  174. 			printf("%d\n", query(u, v));
  175. 		}
  176. 	}
  177. 	return 0;
  178. }
Success #stdin #stdout 0.01s 11140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Rs1pfC
language:
C++ (gcc 8.3)
created:
6 days ago
visibility:
public

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!