fork download
copy 
  1. // God be praised
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int N = 1e4 + 5;
  6. typedef pair<int, int> pii;
  7. pii edges[N];
  8. vector<pii> g[N];
  9. int n;
  10.  
  11. int par[N], euler[2*N], in[N], sz[N], ieu, dep[N];
  12.  
  13. int dfs (int u, int pre, int lvl) {
  14. 	in[u] = ieu;
  15. 	euler[ieu++] = u;
  16. 	sz[u] = 1;
  17. 	dep[u] = lvl;
  18. 	par[u] = pre;
  19.  
  20. 	for (auto &p : g[u]) {
  21. 		int v = p.first;
  22.  
  23. 		if (v == pre) continue;
  24. 		sz[u] += dfs(v, u, lvl+1);
  25. 		euler[ieu++] = u;
  26. 	}
  27.  
  28. 	return sz[u];
  29. }
  30.  
  31. int LCA[15][1<<15];
  32.  
  33. int min_dep(int u, int v) {
  34. 	return (dep[u] < dep[v]) ? u : v;
  35. }
  36.  
  37. void lca_build () {
  38. 	int n = 1;
  39. 	while (n < ieu) n <<= 1;
  40.  
  41. 	int range, half;
  42. 	for (int h = 1; (range = 1 << h) <= n; h++) {
  43. 		half = range >> 1;
  44.  
  45. 		for (int i = half; i < n; i += range) {
  46. 			LCA[h][i-1] = euler[i-1];
  47. 			for (int j = i - 2; j >= i - half; j--) {
  48. 				LCA[h][j] = min_dep(LCA[h][j + 1], euler[j]);
  49. 			}
  50.  
  51. 			LCA[h][i] = euler[i];
  52. 			for (int j = i + 1; j < i + half; j++) {
  53. 				LCA[h][j] = min_dep(LCA[h][j - 1], euler[j]);
  54. 			}
  55. 		}
  56. 	}
  57. }
  58.  
  59. int lca_query (int ql, int qr) {
  60. 	if (ql == qr) {
  61. 		return euler[ql];
  62. 	}
  63.  
  64. 	int h = 32 - __builtin_clz(ql ^ qr);
  65. 	return min_dep(LCA[h][ql], LCA[h][qr]);
  66. }
  67.  
  68. int chain[N], ichain, ord[N], iord, head[N], ordw[N], st[4*N];
  69.  
  70. void hld_dfs (int u, int pre, int w) {
  71. 	iord++;
  72. 	ord[u] = iord;
  73. 	ordw[iord] = w;
  74.  
  75. 	int heavy = -1, weight;
  76. 	for (auto &p : g[u]) {
  77. 		int v = p.first;
  78. 		int vw = p.second;
  79. 		if (v == pre) continue;
  80.  
  81. 		if (heavy == -1 || sz[heavy] < sz[v]) {
  82. 			heavy = v;
  83. 			weight = vw;
  84. 		}
  85. 	}
  86.  
  87. 	if (heavy != -1) {
  88. 		chain[heavy] = chain[u];
  89. 		hld_dfs(heavy, u, weight);
  90. 	}
  91.  
  92. 	for (auto &p : g[u]) {
  93. 		int v = p.first;
  94. 		int vw = p.second;
  95. 		if (v == pre) continue;
  96.  
  97. 		if (v != heavy) {
  98. 			ichain++;
  99. 			chain[v] = ichain;
  100. 			head[ichain] = v;
  101.  
  102. 			hld_dfs(v, u, vw);
  103. 		}
  104. 	}
  105. }
  106.  
  107. int hld_build (int i, int nl, int nr) {
  108. 	if (nl == nr) {
  109. 		return st[i] = ordw[nl];
  110. 	}
  111.  
  112. 	int mid = (nl + nr) / 2;
  113. 	return st[i] = max(
  114. 		hld_build(i+i, nl, mid),
  115. 		hld_build(i+i+1, mid+1, nr)
  116. 	);
  117. }
  118.  
  119. int hld_update (int i, int nl, int nr, int o, int w) {
  120. 	if (nl > o || nr < o) return st[i];
  121.  
  122. 	if (nl == nr) return st[i] = w;
  123.  
  124. 	int mid = (nl + nr) / 2;
  125. 	return st[i] = max(
  126. 		hld_update(i+i, nl, mid, o, w),
  127. 		hld_update(i+i+1, mid+1, nr, o, w)
  128. 	);
  129. }
  130.  
  131. int hld_query (int i, int nl, int nr, int ql, int qr) {
  132. 	if (nl > qr || ql > nr) return INT_MIN;
  133.  
  134. 	if (nl >= ql && nr <= qr) return st[i];
  135.  
  136. 	int mid = (nl + nr) / 2;
  137. 	return max(
  138. 		hld_query(i+i, nl, mid, ql, qr),
  139. 		hld_query(i+i+1, mid+1, nr, ql, qr)
  140. 	);
  141. }
  142.  
  143. int hld_find (int u, int v) {
  144. 	if (u == v) {
  145. 		return INT_MIN;
  146. 	}
  147. 	if (chain[u] == chain[v]) {
  148. 		return hld_query(1, 1, n, ord[u]+1, ord[v]);
  149. 	}
  150. 	return max(
  151. 		hld_query(1, 1, n, ord[head[chain[v]]], ord[v]),
  152. 		hld_find(u, par[head[chain[v]]])
  153. 	);
  154. }
  155.  
  156. char action[20];
  157.  
  158. void change () {
  159. 	int e, w;
  160. 	scanf("%d %d", &e, &w);
  161.  
  162. 	int u, v; tie(u, v) = edges[e];
  163. 	int o = (par[u] == v) ? u : v;
  164. 	hld_update(1, 1, n, ord[o], w);
  165. }
  166.  
  167. void query () {
  168. 	int u, v;
  169. 	scanf("%d %d", &u, &v);
  170.  
  171. 	if (in[u] > in[v]) swap(u, v);
  172. 	int lca = lca_query(in[u], in[v]);
  173.  
  174. 	int ans = max(hld_find(lca, u), hld_find(lca, v));
  175. 	printf("%d\n", ans);
  176. }
  177.  
  178. int main () {
  179. 	// freopen("in.txt", "r", stdin);
  180.  
  181. 	int t;
  182. 	scanf("%d", &t);
  183.  
  184. 	while (t--) {
  185. 		scanf("%d", &n);
  186.  
  187. 		dep[0] = INT_MAX;
  188. 		memset(euler, 0, sizeof euler);
  189. 		for (int i = 1; i <= n; i++) {
  190. 			g[i].clear();
  191. 		}
  192.  
  193. 		for (int i = 1, u, v, w; i < n; i++) {
  194. 			scanf("%d %d %d", &u, &v, &w);
  195. 			g[u].emplace_back(v, w);
  196. 			g[v].emplace_back(u, w);
  197. 			edges[i] = { u, v };
  198. 		}
  199.  
  200. 		ieu = 0;
  201. 		dfs(1, 0, 1);
  202. 		lca_build();
  203.  
  204. 		head[0] = 1;
  205. 		chain[1] = ichain = 0;
  206.  
  207. 		iord = 0;
  208. 		hld_dfs(1, -1, INT_MIN);
  209. 		hld_build(1, 1, iord);
  210.  
  211. 		while (true) {
  212. 			scanf("%s", action);
  213. 			if (*action == 'D'/*DONE*/) break;
  214. 			if (*action == 'C'/*CHANGE*/) change();
  215. 			if (*action == 'Q'/*QUERY*/) query();
  216. 		}
  217. 	}
  218.  
  219. 	return 0;
  220. }
Success #stdin #stdout 0s 4228KB
comments (?)
stdin
copy 
1
11
2 1 13
5 2 4
6 2 25
6 8 5
10 8 1
11 8 6
7 3 29
3 1 9
9 7 30
1 4 23
QUERY 5 6
QUERY 5 1
QUERY 9 11
QUERY 10 4
QUERY 6 7
QUERY 6 3
QUERY 11 8
CHANGE 3 22
QUERY 6 4
QUERY 5 4
QUERY 1 10
QUERY 7 6
DONE
stdout
copy 
25
13
30
25
29
25
6
23
23
22
29
https://ideone.com/nFLWbM
language:
C++14 (gcc 8.3)
created:
5 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!