fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5. const int MAX = 100005;
  6. struct node
  7. {
  8. 	int first, last, sum, len;
  9. 	node()
  10. 	{
  11. 	}
  12. 	node(int _first, int _last, int _sum, int _len)
  13. 	{
  14. 		first = _first;
  15. 		last = _last;
  16. 		sum = _sum;
  17. 		len = _len;
  18. 	}
  19. } seg[4 * MAX];
  20. int f[MAX], n;
  21. node merge(node a, node b)
  22. {
  23. 	node ans;
  24. 	ans.sum = a.sum + b.sum - f[a.last] - f[b.first] + f[a.last + b.first];
  25. 	ans.len = a.len + b.len;
  26. 	ans.first = a.first;
  27. 	if (a.first == a.len)
  28. 		ans.first += b.first;
  29. 	ans.last = b.last;
  30. 	if (b.last == b.len)
  31. 		ans.last += a.last;
  32. 	return ans;
  33. }
  34. void build(int v = 1, int s = 0, int e = n)
  35. {
  36. 	seg[v].first = seg[v].last = seg[v].sum = 0;
  37. 	seg[v].len = e - s;
  38. 	if (e - s < 2)
  39. 		return;
  40. 	int mid = (s + e) / 2;
  41. 	build(2 * v, s, mid);
  42. 	build(2 * v + 1, mid, e);
  43. }
  44. void add(int p, int v = 1, int s = 0, int e = n)
  45. {
  46. 	if (e - s < 2)
  47. 	{
  48. 		seg[v].first = seg[v].last = 1;
  49. 		seg[v].sum = f[1];
  50. 		return;
  51. 	}
  52. 	int mid = (s + e) / 2;
  53. 	if (p < mid)
  54. 		add(p, 2 * v, s, mid);
  55. 	else
  56. 		add(p, 2 * v + 1, mid, e);
  57. 	seg[v] = merge(seg[2 * v], seg[2 * v + 1]);
  58. }
  59. node get(int l, int r, int v = 1, int s = 0, int e = n)
  60. {
  61. 	if (l <= s && e <= r)
  62. 		return seg[v];
  63. 	if (e <= l || r <= s)
  64. 		return node(0, 0, 0, 0);
  65. 	int mid = (s + e) / 2;
  66. 	return merge(get(l, r, 2 * v, s, mid), get(l, r, 2 * v + 1, mid, e));
  67. }
  68. int size[MAX], par[17][MAX], d[MAX], len[MAX], head[MAX], length[MAX], start[MAX];
  69. vector<int> adj[MAX];
  70. void pre(int p, int v)
  71. {
  72. 	par[0][v] = p;
  73. 	for (int i = 1; i < 17; i++)
  74. 		par[i][v] = par[i - 1][par[i - 1][v]];
  75. 	size[v] = 1;
  76. 	for (int i = 0; i < adj[v].size(); i++)
  77. 	{
  78. 		int u = adj[v][i];
  79. 		if (u != p)
  80. 		{
  81. 			d[u] = d[v] + 1;
  82. 			pre(v, u);
  83. 			size[v] += size[u];
  84. 		}
  85. 	}
  86. }
  87. void hld(int p, int v)
  88. {
  89. 	if (head[v] != v)
  90. 		length[head[v]]++;
  91. 	int mx = -1;
  92. 	for (int i = 0; i < adj[v].size(); i++)
  93. 	{
  94. 		int u = adj[v][i];
  95. 		if (u == p)
  96. 			continue;
  97. 		if (mx == -1 || size[mx] < size[u])
  98. 			mx = u;
  99. 	}
  100. 	if (mx != -1)
  101. 		head[mx] = head[v];
  102. 	for (int i = 0; i < adj[v].size(); i++)
  103. 	{
  104. 		int u = adj[v][i];
  105. 		if (u != p)
  106. 			hld(v, u);
  107. 	}
  108. }
  109. int get_parent(int v, int k)
  110. {
  111. 	for (int i = 0; i < 17; i++)
  112. 		if ((1 << i) & k)
  113. 			v = par[i][v];
  114. 	return v;
  115. }
  116. int lca(int u, int v)
  117. {
  118. 	if (d[u] < d[v])
  119. 		swap(u, v);
  120. 	u = get_parent(u, d[u] - d[v]);
  121. 	if (u == v)
  122. 		return u;
  123. 	for (int i = 16; i >= 0; i--)
  124. 		if (par[i][u] != par[i][v])
  125. 		{
  126. 			u = par[i][u];
  127. 			v = par[i][v];
  128. 		}
  129. 	return par[0][v];
  130. }
  131. void active(int u, int v)
  132. {
  133. 	if (d[u] < d[v])
  134. 		swap(u, v);
  135. 	if (head[u] != u)
  136. 		add(start[head[u]] + d[u] - d[head[u]] - 1);
  137. 	else
  138. 		len[u]++;
  139. }
  140. node get_path(int x, int y)
  141. {
  142. 	node ans(0, 0, 0, 0);
  143. 	while (d[x] > d[y])
  144. 	{
  145. 		if (head[x] == x)
  146. 		{
  147. 			if (len[x])
  148. 				ans = merge(node(1, 1, f[1], 1), ans);
  149. 			else
  150. 				ans = merge(node(0, 0, 0, 1), ans);
  151. 			x = par[0][x];
  152. 		}
  153. 		else
  154. 		{
  155. 			int r = start[head[x]] + d[x] - d[head[x]];
  156. 			int l = start[head[x]];
  157. 			if (head[x] == head[y])
  158. 				l = start[head[y]] + d[y] - d[head[y]];
  159. 			ans = merge(get(l, r), ans);
  160. 			x = head[x];
  161. 		}
  162. 	}
  163. 	return ans;
  164. }
  165. vector<pair<int, pair<int, int> > > edges;
  166. pair<int, pair<pair<int, int>, int> > qq[MAX];
  167. int ans[MAX];
  168. int main()
  169. {
  170. 	ios::sync_with_stdio(false);
  171. 	for (int i = 0; i < MAX; i++)
  172. 		head[i] = i;
  173. 	int q;
  174. 	cin >> n >> q;
  175. 	build();
  176. 	for (int i = 1; i < n; i++)
  177. 		cin >> f[i];
  178. 	for (int i = 0; i < n - 1; i++)
  179. 	{
  180. 		int u, v, w;
  181. 		cin >> u >> v >> w;
  182. 		u--;
  183. 		v--;
  184. 		edges.push_back(make_pair(w, make_pair(u, v)));
  185. 		adj[u].push_back(v);
  186. 		adj[v].push_back(u);
  187. 	}
  188. 	pre(0, 0);
  189. 	hld(0, 0);
  190. 	int cnt = 0;
  191. 	for (int i = 0; i < n; i++)
  192. 		if (head[i] == i)
  193. 		{
  194. 			start[i] = cnt;
  195. 			cnt += length[i];
  196. 		}
  197. 	for (int i = 0; i < q; i++)
  198. 	{
  199. 		cin >> qq[i].second.first.first >> qq[i].second.first.second >> qq[i].first;
  200. 		qq[i].second.second = i;
  201. 	}
  202. 	sort(edges.begin(), edges.end());
  203. 	reverse(edges.begin(), edges.end());
  204. 	sort(qq, qq + q);
  205. 	reverse(qq, qq + q);
  206. 	int ptr = 0;
  207. 	for (int i = 0; i < q; i++)
  208. 	{
  209. 		while (ptr < edges.size() && edges[ptr].first >= qq[i].first)
  210. 		{
  211. 			active(edges[ptr].second.first, edges[ptr].second.second);
  212. 			ptr++;
  213. 		}
  214. 		int u = qq[i].second.first.first;
  215. 		int v = qq[i].second.first.second;
  216. 		u--;
  217. 		v--;
  218. 		int p = lca(u, v);
  219. 		if (u == p)
  220. 			swap(v, u);
  221. 		node res;
  222. 		node x = get_path(v, p);
  223. 		node y = get_path(u, p);
  224. 		swap(x.first, x.last);
  225. 		res = merge(x, y);
  226. 		ans[qq[i].second.second] = res.sum;
  227. 	}
  228. 	for (int i = 0; i < q; i++)
  229. 		cout << ans[i] << '\n';
  230. 	return 0;
  231. }
Runtime error #stdin #stdout 0s 22000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7blKHl
language:
C++14 (gcc 8.3)
created:
9 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!