fork download
copy 
  1. /**
  2.  * Problem : QTREE - Query on a tree
  3.  * Problem URL : https://w...content-available-to-author-only...j.com/problems/QTREE/
  4.  */
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. using ll = long long;
  9. using pii = pair < int, int >;
  10.  
  11. // This section is for Policy Based Data Structure, more precisely Ordered Set.
  12. // All Functions of set works here, in addition we have order_of_key() and find_by_order() function. find_by_order() returns iterator
  13. #include<ext/pb_ds/assoc_container.hpp>
  14. #include<ext/pb_ds/tree_policy.hpp>
  15. #include<functional>
  16. using namespace __gnu_pbds;
  17.  
  18. // 1. Custom Set
  19. template < class T, class COMP >
  20. using custom_set = tree < T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update >;
  21.  
  22. // 2. Ordered Set
  23. template < class T >
  24. using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
  25.  
  26. // 3. Ordered Multi Set
  27. // For storing multiple occurance of same value we need to use pair. In pair first value is our key and second is useless count variable.
  28. // order_of_key(make_pair(key, 0)) returns first occurance of a value, order_of_key(make_pair(key, INT_MAX)) returns last occurance.
  29. template < class T >
  30. using ordered_multiset = tree < pair < T, int >, null_type, less < pair < T, int > >, rb_tree_tag, tree_order_statistics_node_update >;
  31.  
  32. // 4. Ordered Map
  33. template < class T, class U >
  34. using ordered_map = tree < T, U, less < T >, rb_tree_tag, tree_order_statistics_node_update >;
  35. // Policy End
  36.  
  37. const int mx = 10005;
  38. const int BITS = 14;
  39.  
  40. vector < pii > adj[mx];
  41. pii edges[mx];
  42. int SA[mx], ST[6 * mx];
  43. int nodes[mx][5];
  44. int edgeCount, currentChain, n, chainHeads[mx];
  45. int tin[mx], tout[mx], up[mx][BITS], timer;
  46.  
  47. void addEdge (int id, int u, int v, int w) {
  48. 	adj[u].emplace_back (v, id);
  49. 	adj[v].emplace_back (u, id);
  50. 	edges[id].first = w;
  51. }
  52.  
  53. void dfs (int u, int p, int d) {
  54. 	nodes[u][0] = p, nodes[u][1] = d, nodes[u][2] = 1;
  55. 	tin[u] = timer++;
  56. 	if (p == -1)
  57. 		up[u][0] = u;
  58. 	else
  59. 		up[u][0] = p;
  60. 	for (int i = 1; i < BITS; i++) {
  61. 		up[u][i] = up[up[u][i - 1]][i - 1];
  62. 	}
  63. 	for (pii & pi : adj[u]) {
  64. 		if (pi.first != p) {
  65. 			dfs (pi.first, u, d + 1);
  66. 			nodes[u][2]++;
  67. 			edges[pi.second].second = pi.first;
  68. 		}
  69. 	}
  70. 	tout[u] = timer;
  71. }
  72.  
  73. void HLD (int u, int id) {
  74. 	if (chainHeads[currentChain] == -1) {
  75. 		chainHeads[currentChain] = u;
  76. 	}
  77. 	nodes[u][4] = currentChain;
  78. 	nodes[u][3] = edgeCount;
  79. 	SA[edgeCount++] = edges[id].first;
  80. 	int sc = -1, si;
  81. 	for (pii & pi : adj[u]) {
  82. 		if (pi.first != nodes[u][0]) {
  83. 			if (sc == -1 || nodes[sc][2] < nodes[pi.first][2]) {
  84. 				sc = pi.first; si = pi.second;
  85. 			}
  86. 		}
  87. 	}
  88. 	if (sc != -1) {
  89. 		HLD (sc, si);
  90. 	}
  91.  
  92. 	for (pii & pi : adj[u]) {
  93. 		if (pi.first != nodes[u][0] && pi.first != sc) {
  94. 			currentChain++;
  95. 			HLD (pi.first, pi.second);
  96. 		}
  97. 	}
  98. }
  99.  
  100. bool is_ancestor (int u, int v) {
  101. 	return tin[u] <= tin[v] && tout[u] >= tout[v];
  102. }
  103.  
  104. int LCA (int u, int v) {
  105. 	if (is_ancestor (u, v)) return u;
  106. 	if (is_ancestor (v, u)) return v;
  107. 	for (int i = BITS - 1; i >= 0; i--) {
  108. 		if (!is_ancestor (up[u][i], v))
  109. 			u = up[u][i];
  110. 	}
  111. 	return up[u][0];
  112. }
  113.  
  114. void build (int low, int high, int pos) {
  115. 	if (low == high) {
  116. 		ST[pos] = SA[low];
  117. 		return;
  118. 	}
  119. 	int mid = low + high;
  120. 	mid >>= 1;
  121. 	int pos1 = (pos << 1) + 1;
  122. 	int pos2 = pos1 + 1;
  123. 	build (low, mid, pos1);
  124. 	build (mid + 1, high, pos2);
  125. 	ST[pos] = ST[pos1] > ST[pos2] ? ST[pos1] : ST[pos2];
  126. }
  127.  
  128. void updateUtil (int low, int high, int index, int value, int pos) {
  129. 	if (low > index || high < index) return;	
  130. 	if (low == high) {
  131. 		ST[pos] = value;
  132. 		return;
  133. 	}
  134. 	int mid = low + high;
  135. 	mid >>= 1;
  136. 	int pos1 = (pos << 1)  + 1;
  137. 	int pos2 = pos1 + 1;
  138. 	updateUtil (low, mid, index, value, pos1);
  139. 	updateUtil (mid + 1, high, index, value, pos2);
  140. 	ST[pos] = ST[pos1] > ST[pos2] ? ST[pos1] : ST[pos2];
  141. }
  142.  
  143. void update (int id, int value) {
  144. 	updateUtil (0, n - 1, nodes[edges[id].second][3], value, 0);
  145. }
  146.  
  147. int queryUtil (int low, int high, int left, int right, int pos) {
  148. 	if (left <= low && right >= high) return ST[pos];
  149. 	if (left > high || low > right) return -1;
  150. 	int mid = low + high;
  151. 	mid >>= 1;
  152. 	int pos1 = (pos << 1)  + 1;
  153. 	int pos2 = pos1 + 1;
  154. 	int a = queryUtil (low, mid, left, right, pos1);
  155. 	int b = queryUtil (mid + 1, high, left, right, pos2);
  156. 	return a > b ? a : b;
  157. }
  158.  
  159. int query (int left, int right) {
  160. 	return queryUtil (0, n - 1, left, right, 0);
  161. }
  162.  
  163. int crawlTree (int u, int v) {
  164. 	int cu, cv = nodes[v][4], ans = 0;
  165. 	while (true) {
  166. 		cu = nodes[u][4];
  167. 		if (cu == cv) {
  168. 			if (u != v) {
  169. 				int a = query (nodes[v][3] + 1, nodes[u][3]);
  170. 				if (ans < a) ans = a;
  171. 			}
  172. 			break;
  173. 		} else {
  174. 			int a = query (nodes[chainHeads[cu]][3], nodes[u][3]);
  175. 			if (ans < a) ans = a;
  176. 			u = nodes[chainHeads[cu]][0];
  177. 		}
  178. 	}
  179. 	return ans;
  180. }
  181.  
  182. int maxEdge (int u, int v) {
  183. 	int lca = LCA (u, v);
  184. 	// cerr << "LCA (" << u + 1 << ", " << v + 1 << ") = " << lca + 1 << endl;
  185. 	int a = crawlTree (u, lca);
  186. 	int b = crawlTree (v, lca);
  187. 	return a > b ? a : b;
  188. }
  189.  
  190. void solve () {
  191. 	scanf ("%d", &n);
  192. 	/**
  193. 		vector < pii > adj[mx];
  194. 		pii edges[mx];
  195. 		SegmentTree S;
  196. 		TreeNode node[mx];
  197. 		int edgeCount, currentChain, n, chainHeads[mx];
  198. 		int tin[mx], tout[mx], up[mx][BITS];
  199. 	*/
  200. 	for (int i = 0; i < n; i++) {
  201. 		adj[i].clear();
  202. 	}
  203. 	memset (chainHeads, -1, sizeof (chainHeads));
  204. 	edgeCount = currentChain = timer = 0;
  205. 	int u, v, w;
  206. 	for (int i = 0; i < n - 1; i++) {
  207. 		// cin >> u >> v >> w;
  208. 		scanf ("%d %d %d", &u, &v, &w);
  209. 		u--, v--;
  210. 		addEdge (i, u, v, w);
  211. 	}
  212. 	int root = 0, p = -1, d = 0;
  213. 	dfs (root, p, d);
  214. 	edges[n - 1] = {-1, -1};
  215. 	HLD (root, n - 1);
  216. 	build (0, edgeCount - 1, 0);
  217. 	// for (int i = 0; i < n; i++) {
  218. 		// for (int j = 0; j < n; j++) {
  219. 			// cerr << i << " -- " << j << " => " << maxEdge (i, j) << endl;
  220. 		// }
  221. 	// }
  222. 	// for (int i = 0; i < n - 1; i++) {
  223. 		// update (i, 1);
  224. 	// }
  225. 	// string s;
  226. 	while (true) {
  227. 		char s[10];
  228. 		scanf ("%s", s);
  229. 		// cin >> s;
  230. 		if (s[0] == 'D') {
  231. 			break;
  232. 		}
  233. 		if (s[0] == 'C') {
  234. 			// cin >> u >> v;
  235. 			scanf ("%d %d", &u, &v);
  236. 			u--;
  237. 			update (u, v);
  238. 		} else {
  239. 			// cin >> u >> v;
  240. 			scanf ("%d %d", &u, &v);
  241. 			u--, v--;
  242. 			cout << maxEdge (u, v) << endl;
  243. 		}
  244. 	}
  245. }
  246.  
  247. int main() {
  248. 	// ios_base::sync_with_stdio (false);
  249. 	// cin.tie (nullptr); cout.tie(nullptr);
  250. 	int t = 1;
  251. 	scanf ("%d", &t);
  252. 	while (t--) {
  253. 		solve();
  254. 	}
  255. 	return 0;
  256. }
  257.  
  258.  
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
3

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

11
1 2 13
1 3 9
1 4 23
2 5 4
2 6 25
3 7 29
6 8 5
7 9 30
8 10 1
8 11 6
QUERY 11 9
CHANGE 8 28
QUERY 11 9
QUERY 11 4
CHANGE 5 22
QUERY 11 4
DONE
stdout
copy 
1
3
1
3
30
29
25
23
https://ideone.com/Fbh9uc
language:
C++14 (gcc 8.3)
created:
4 years 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!