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. void update(int node, int start, int end, int idx, int val)
  79. {
  80. 	if(start == end)
  81. 	{
  82. 		t[node] = b[start] = val;
  83. 		return ;
  84. 	}
  85. 	int mid = (start + end)/2;
  86. 	if(idx <= mid)update(2*node, start, mid, idx, val);
  87. 	else update(2*node + 1, mid + 1, end, idx, val);
  88. }
  89.  
  90. int find(int a, int b)
  91. {
  92. 	int res = 0;
  93. 	while(root[a] != root[b])
  94. 	{
  95. 		if(depth[root[a]] < depth[root[b]])
  96. 			swap(a, b);
  97. 		res = max(res, query(1, 0, n-1, num[root[a]], num[a]));
  98. 		a = p[root[a]];
  99. 	}
  100. 	if(depth[a] > depth[b])
  101. 		swap(a, b);
  102. 	res = max(res, query(1, 0, n-1, num[a] + 1, num[b]));
  103. 	return res;
  104. }
  105.  
  106. int main()
  107. {
  108. 	// freopen("in.txt", "r", stdin);
  109.  
  110. 	int t;
  111. 	scanf("%d", &t);
  112. 	while(t--)
  113. 	{
  114. 		scanf("%d", &n);
  115. 		for(int i=0;i<n;++i) {
  116. 			heavy[i] = -1;
  117. 			g[i].clear();
  118. 		}
  119. 		for(int i=0;i<n -1;++i)
  120. 		{
  121. 			int a, b, c;
  122. 			scanf("%d %d %d", &a, &b, &c); a--; b--;
  123. 			g[a].push_back(mp(b, mp(c, i) ) );
  124. 			g[b].push_back(mp(a, mp(c, i) ) );
  125. 		}
  126. 		a[0] = 0;
  127. 		dfs(0); hld(); build(1, 0, n-1);
  128.  
  129. 		while(1)
  130. 		{
  131. 			char s[10];
  132. 			scanf("%s", s);
  133. 			if(s[0] == 'D')break;
  134. 			else if(s[0] == 'C')
  135. 			{
  136. 				int i, ti;
  137. 				scanf("%d %d", &i, &ti); i--;
  138. 				update(1, 0, n-1, num[vtx[i]], ti);
  139. 			}
  140. 			else
  141. 			{
  142. 				int a, b;
  143. 				scanf("%d %d", &a, &b); a--; b--;
  144. 				printf("%d\n", find(a, b));
  145. 			}
  146. 		}
  147. 	}
  148. 	return 0;
  149. }
Success #stdin #stdout 0s 4252KB
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/4aHr1u
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!