fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define X first 
  6. #define Y second 
  7. #define mp make_pair
  8.  
  9. const int N = 20000;
  10.  
  11. int n, heavy[N], root[N], p[N];
  12. int num[N], depth[N], t[6*N], a[N], b[N], vtx[N];
  13.  
  14. vector<pair<int, pair<int, int> > > g[N];
  15.  
  16. int dfs(int v = 0, int prnt = -1, int d = 0)
  17. {
  18. 	int size = 1, MAXsize = 0;
  19. 	depth[v] = d;
  20. 	p[v] = prnt;
  21. 	for(int i=0;i<g[v].size();++i)
  22. 	{
  23. 		int u = g[v][i].X;
  24. 		int c = g[v][i].Y.X , idx = g[v][i].Y.Y;
  25. 		if(u != prnt)
  26. 		{
  27. 			int subsize = dfs(u, v, d + 1);
  28. 			if(subsize > MAXsize)
  29. 			{
  30. 				MAXsize = subsize;
  31. 				heavy[v] = u;
  32. 			}
  33. 			vtx[idx] = u;
  34. 			size += subsize;
  35. 			a[u] = c;
  36. 		}
  37. 	}
  38. 	return size;
  39. }
  40.  
  41. void hld()
  42. {
  43. 	for(int i=0, currpos = 0; i < n; ++i)
  44. 		if(p[i] == -1 || heavy[p[i]] != i)
  45. 			for(int j = i; j != -1; j = heavy[j])
  46. 			{
  47. 				root[j] = i;
  48. 				num[j] = currpos; b[currpos] = a[j];
  49. 				currpos++;
  50. 			}
  51. }
  52.  
  53. void build(int node, int start, int end)
  54. {
  55. 	if(start == end)
  56. 	{
  57. 		t[node] = b[start];
  58. 		return ;
  59. 	}
  60. 	int mid = (start + end)/2;
  61. 	build(2*node, start, mid);
  62. 	build(2*node + 1, mid + 1, end);
  63. 	t[node] = t[2*node] > t[2*node + 1] ? t[2*node] : t[2*node + 1];
  64. }
  65.  
  66. int query(int node, int start, int end, int l, int r)
  67. {
  68. 	if(end < l || start > r)
  69. 		return 0;
  70. 	if(start >= l && end <= r)
  71. 		return t[node];
  72. 	int mid = (start + end)/2;
  73. 	int p1 = query(2*node, start, mid, l, r);
  74. 	int p2 = query(2*node + 1, mid + 1, end, l, r);
  75. 	return (p1 > p2 ? p1 : p2);
  76. }
  77.  
  78. int update(int node, int start, int end, int idx, int val) {
  79. 	if (idx < start || idx > end) return t[node];
  80. 	if (start == end) return t[node] = b[start] = val;
  81.  
  82. 	int mid = (start + end) / 2;
  83. 	return t[node] = max(
  84. 		update(2*node, start, mid, idx, val),
  85. 		update(2*node + 1, mid + 1, end, idx, val)
  86. 	);
  87. }
  88.  
  89. int find(int a, int b)
  90. {
  91. 	int res = 0;
  92. 	while(root[a] != root[b])
  93. 	{
  94. 		if(depth[root[a]] < depth[root[b]])
  95. 			swap(a, b);
  96. 		res = max(res, query(1, 0, n-1, num[root[a]], num[a]));
  97. 		a = p[root[a]];
  98. 	}
  99. 	if(depth[a] > depth[b])
  100. 		swap(a, b);
  101. 	res = max(res, query(1, 0, n-1, num[a] + 1, num[b]));
  102. 	return res;
  103. }
  104.  
  105. int main()
  106. {
  107. 	// freopen("in.txt", "r", stdin);
  108.  
  109. 	int t;
  110. 	scanf("%d", &t);
  111. 	while(t--)
  112. 	{
  113. 		scanf("%d", &n);
  114. 		for(int i=0;i<n;++i) {
  115. 			heavy[i] = -1;
  116. 			g[i].clear();
  117. 		}
  118. 		for(int i=0;i<n -1;++i)
  119. 		{
  120. 			int a, b, c;
  121. 			scanf("%d %d %d", &a, &b, &c); a--; b--;
  122. 			g[a].push_back(mp(b, mp(c, i) ) );
  123. 			g[b].push_back(mp(a, mp(c, i) ) );
  124. 		}
  125. 		a[0] = 0;
  126. 		dfs(0); hld(); build(1, 0, n-1);
  127.  
  128. 		while(1)
  129. 		{
  130. 			char s[10];
  131. 			scanf("%s", s);
  132. 			if(s[0] == 'D')break;
  133. 			else if(s[0] == 'C')
  134. 			{
  135. 				int i, ti;
  136. 				scanf("%d %d", &i, &ti); i--;
  137. 				update(1, 0, n-1, num[vtx[i]], ti);
  138. 			}
  139. 			else
  140. 			{
  141. 				int a, b;
  142. 				scanf("%d %d", &a, &b); a--; b--;
  143. 				printf("%d\n", find(a, b));
  144. 			}
  145. 		}
  146. 	}
  147. 	return 0;
  148. }
Success #stdin #stdout 0s 4484KB
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/adVFFN
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!