fork(6) 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 + 1]) ? 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. 	t[node] = t[2*node] > t[2*node + 1] ? t[2*node] : t[2*node + 1];
  90. }
  91.  
  92. int find(int a, int b)
  93. {
  94. 	int res = 0;
  95. 	while(root[a] != root[b])
  96. 	{
  97. 		if(depth[root[a]] < depth[root[b]])
  98. 			swap(a, b);
  99. 		res = MAX(res, query(1, 0, n-1, num[root[a]], num[a]));
  100. 		a = p[root[a]];
  101. 	}
  102. 	if(depth[a] > depth[b])
  103. 		swap(a, b);
  104. 	res = MAX(res, query(1, 0, n-1, num[a] + 1, num[b]));
  105. 	return res;
  106. }
  107.  
  108. int main()
  109. {
  110. 	int t;
  111. 	scanf("%d", &t);
  112. 	while(t--)
  113. 	{
  114. 		scanf("%d", &n);
  115. 		for(int i=0;i<n -1;++i)
  116. 		{
  117. 			int a, b, c;
  118. 			scanf("%d %d %d", &a, &b, &c); a--; b--;
  119. 			g[a].push_back(mp(b, mp(c, i) ) );
  120. 			g[b].push_back(mp(a, mp(c, i) ) );
  121. 		}
  122. 		for(int i=0;i<n;++i)
  123. 			heavy[i] = -1;
  124. 		a[0] = 0;
  125. 		dfs(0); hld(); build(1, 0, n-1);
  126. 		while(1)
  127. 		{
  128. 			char s[10];
  129. 			scanf("%s", s);
  130. 			if(s[0] == 'D')break;
  131. 			else if(s[0] == 'C')
  132. 			{
  133. 				int i, ti;
  134. 				scanf("%d %d", &i, &ti); i--;
  135. 				update(1, 0, n-1, num[vtx[i]], ti);
  136. 			}
  137. 			else
  138. 			{
  139. 				int a, b;
  140. 				scanf("%d %d", &a, &b); a--; b--;
  141. 				printf("%d\n", find(a, b));
  142. 			}
  143. 		}
  144. 		for(int i=0;i<n;++i)
  145. 			g[i].clear();
  146. 	}
  147. 	return 0;
  148. }
Time limit exceeded #stdin #stdout 5s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ykg63S
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!