fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. #define root 0
  6. #define N 10100
  7. #define LN 14
  8.  
  9. vector <int> adj[N], costs[N], indexx[N];
  10. int baseArray[N], ptr;
  11. int chainNo, chainInd[N], chainHead[N], posInBase[N];
  12. int depth[N], pa[LN][N], otherEnd[N], subsize[N];
  13. int st[N*6], qt[N*6];
  14.  
  15. /*
  16.  * make_tree:
  17.  * Used to construct the segment tree. It uses the baseArray for construction
  18.  */
  19. void make_tree(int cur, int s, int e) {
  20. 	if(s == e-1) {
  21. 		st[cur] = baseArray[s];
  22. 		return;
  23. 	}
  24. 	int c1 = (cur<<1), c2 = c1 | 1, m = (s+e)>>1;
  25. 	make_tree(c1, s, m);
  26. 	make_tree(c2, m, e);
  27. 	st[cur] = st[c1] > st[c2] ? st[c1] : st[c2];
  28. }
  29.  
  30. /*
  31.  * update_tree:
  32.  * Point update. Update a single element of the segment tree.
  33.  */
  34. void update_tree(int cur, int s, int e, int x, int val) {
  35. 	if(s > x || e <= x) return;
  36. 	if(s == x && s == e-1) {
  37. 		st[cur] = val;
  38. 		return;
  39. 	}
  40. 	int c1 = (cur<<1), c2 = c1 | 1, m = (s+e)>>1;
  41. 	update_tree(c1, s, m, x, val);
  42. 	update_tree(c2, m, e, x, val);
  43. 	st[cur] = st[c1] > st[c2] ? st[c1] : st[c2];
  44. }
  45.  
  46. /*
  47.  * query_tree:
  48.  * Given S and E, it will return the maximum value in the range [S,E)
  49.  */
  50. void query_tree(int cur, int s, int e, int S, int E) {
  51. 	if(s >= E || e <= S) {
  52. 		qt[cur] = -1;
  53. 		return;
  54. 	}
  55. 	if(s >= S && e <= E) {
  56. 		qt[cur] = st[cur];
  57. 		return;
  58. 	}
  59. 	int c1 = (cur<<1), c2 = c1 | 1, m = (s+e)>>1;
  60. 	query_tree(c1, s, m, S, E);
  61. 	query_tree(c2, m, e, S, E);
  62. 	qt[cur] = qt[c1] > qt[c2] ? qt[c1] : qt[c2];
  63. }
  64.  
  65. /*
  66.  * query_up:
  67.  * It takes two nodes u and v, condition is that v is an ancestor of u
  68.  * We query the chain in which u is present till chain head, then move to next chain up
  69.  * We do that way till u and v are in the same chain, we query for that part of chain and break
  70.  */
  71.  
  72. int query_up(int u, int v) {
  73. 	if(u == v) return 0; // Trivial
  74. 	int uchain, vchain = chainInd[v], ans = -1;
  75. 	// uchain and vchain are chain numbers of u and v
  76. 	while(1) {
  77. 		uchain = chainInd[u];
  78. 		if(uchain == vchain) {
  79. 			// Both u and v are in the same chain, so we need to query from u to v, update answer and break.
  80. 			// We break because we came from u up till v, we are done
  81. 			if(u==v) break;
  82. 			query_tree(1, 0, ptr, posInBase[v]+1, posInBase[u]+1);
  83. 			// Above is call to segment tree query function
  84. 			if(qt[1] > ans) ans = qt[1]; // Update answer
  85. 			break;
  86. 		}
  87. 		query_tree(1, 0, ptr, posInBase[chainHead[uchain]], posInBase[u]+1);
  88. 		// Above is call to segment tree query function. We do from chainHead of u till u. That is the whole chain from
  89. 		// start till head. We then update the answer
  90. 		if(qt[1] > ans) ans = qt[1];
  91. 		u = chainHead[uchain]; // move u to u's chainHead
  92. 		u = pa[0][u]; //Then move to its parent, that means we changed chains
  93. 	}
  94. 	return ans;
  95. }
  96.  
  97. /*
  98.  * LCA:
  99.  * Takes two nodes u, v and returns Lowest Common Ancestor of u, v
  100.  */
  101. int LCA(int u, int v) {
  102.  
  103. 	while(chainInd[u] != chainInd[v]){
  104.  
  105. 		if (depth[chainHead[chainInd[u]]] > depth[chainHead[chainInd[v]]])
  106. 			u = pa[0][chainHead[chainInd[u]]];
  107. 		else
  108. 			v = pa[0][chainHead[chainInd[v]]];
  109.  
  110. 	}
  111.  
  112. 	if(depth[u] > depth[v])
  113. 		return v;
  114. 	return u;
  115.  
  116. }
  117.  
  118. void query(int u, int v) {
  119. 	/*
  120. 	 * We have a query from u to v, we break it into two queries, u to LCA(u,v) and LCA(u,v) to v
  121. 	 */
  122. 	int lca = LCA(u, v);
  123. 	int ans = query_up(u, lca); // One part of path
  124. 	int temp = query_up(v, lca); // another part of path
  125. 	if(temp > ans) ans = temp; // take the maximum of both paths
  126. 	printf("%d\n", ans);
  127. }
  128.  
  129. /*
  130.  * change:
  131.  * We just need to find its position in segment tree and update it
  132.  */
  133. void change(int i, int val) {
  134. 	int u = otherEnd[i];
  135. 	update_tree(1, 0, ptr, posInBase[u], val);
  136. }
  137.  
  138. /*
  139.  * Actual HL-Decomposition part
  140.  * Initially all entries of chainHead[] are set to -1.
  141.  * So when ever a new chain is started, chain head is correctly assigned.
  142.  * As we add a new node to chain, we will note its position in the baseArray.
  143.  * In the first for loop we find the child node which has maximum sub-tree size.
  144.  * The following if condition is failed for leaf nodes.
  145.  * When the if condition passes, we expand the chain to special child.
  146.  * In the second for loop we recursively call the function on all normal nodes.
  147.  * chainNo++ ensures that we are creating a new chain for each normal child.
  148.  */
  149. void HLD(int curNode, int cost, int prev) {
  150. 	if(chainHead[chainNo] == -1) {
  151. 		chainHead[chainNo] = curNode; // Assign chain head
  152. 	}
  153. 	chainInd[curNode] = chainNo;
  154. 	posInBase[curNode] = ptr; // Position of this node in baseArray which we will use in Segtree
  155. 	baseArray[ptr++] = cost;
  156.  
  157. 	int sc = -1, ncost;
  158. 	// Loop to find special child
  159. 	for(int i=0; i<adj[curNode].size(); i++) if(adj[curNode][i] != prev) {
  160. 		if(sc == -1 || subsize[sc] < subsize[adj[curNode][i]]) {
  161. 			sc = adj[curNode][i];
  162. 			ncost = costs[curNode][i];
  163. 		}
  164. 	}
  165.  
  166. 	if(sc != -1) {
  167. 		// Expand the chain
  168. 		HLD(sc, ncost, curNode);
  169.  
  170. 		for(int i=0; i<adj[curNode].size(); i++) if(adj[curNode][i] != prev) {
  171. 			if(sc != adj[curNode][i]) {
  172. 			// New chains at each normal node
  173. 				chainNo++;
  174. 				HLD(adj[curNode][i], costs[curNode][i], curNode);
  175. 			}
  176. 		}
  177. 	}
  178. }
  179.  
  180. /*
  181.  * dfs used to set parent of a node, depth of a node, subtree size of a node
  182.  */
  183. void dfs(int cur, int prev, int _depth=0) {
  184. 	pa[0][cur] = prev;
  185. 	depth[cur] = _depth;
  186. 	subsize[cur] = 1;
  187. 	for(int i=0; i<adj[cur].size(); i++)
  188. 		if(adj[cur][i] != prev) {
  189. 			otherEnd[indexx[cur][i]] = adj[cur][i];
  190. 			dfs(adj[cur][i], cur, _depth+1);
  191. 			subsize[cur] += subsize[adj[cur][i]];
  192. 		}
  193. }
  194.  
  195. int main() {
  196. 	int t;
  197. 	scanf("%d ", &t);
  198. 	while(t--) {
  199. 		ptr = 0;
  200. 		int n;
  201. 		scanf("%d", &n);
  202. 		// Cleaning step, new test case
  203. 		for(int i=0; i<n; i++) {
  204. 			adj[i].clear();
  205. 			costs[i].clear();
  206. 			indexx[i].clear();
  207. 			chainHead[i] = -1;
  208. 			for(int j=0; j<LN; j++) pa[j][i] = -1;
  209. 		}
  210. 		for(int i=1; i<n; i++) {
  211. 			int u, v, c;
  212. 			scanf("%d %d %d", &u, &v, &c);
  213. 			u--; v--;
  214. 			adj[u].push_back(v);
  215. 			costs[u].push_back(c);
  216. 			indexx[u].push_back(i-1);
  217. 			adj[v].push_back(u);
  218. 			costs[v].push_back(c);
  219. 			indexx[v].push_back(i-1);
  220. 		}
  221.  
  222. 		chainNo = 0;
  223. 		dfs(root, -1); // We set up subsize, depth and parent for each node
  224. 		HLD(root, -1, -1); // We decomposed the tree and created baseArray
  225. 		make_tree(1, 0, ptr); // We use baseArray and construct the needed segment tree
  226.  
  227. 		while(1) {
  228. 			char s[100];
  229. 			scanf("%s", s);
  230. 			if(s[0]=='D') {
  231. 				break;
  232. 			}
  233. 			int a, b;
  234. 			scanf("%d %d", &a, &b);
  235. 			if(s[0]=='Q') {
  236. 				query(a-1, b-1);
  237. 			} else {
  238. 				change(a-1, b);
  239. 			}
  240. 		}
  241. 	}
  242. }
Success #stdin #stdout 0s 5132KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/8jDcCl
language:
C++ (gcc 8.3)
created:
7 years 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!