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