fork download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <sstream>
  4.  
  5. #include <vector>
  6. #include <set>
  7. #include <bitset>
  8. #include <map>
  9. #include <deque>
  10. #include <string>
  11.  
  12. #include <algorithm>
  13. #include <numeric>
  14.  
  15. #include <cstdio>
  16. #include <cassert>
  17. #include <cstdlib>
  18. #include <cstring>
  19. #include <ctime>
  20. #include <cmath>
  21.  
  22. #define pb push_back
  23. #define pbk pop_back
  24. #define mp make_pair
  25. #define fs first
  26. #define sc second
  27. #define all(x) (x).begin(), (x).end()
  28. #define foreach(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
  29. #define len(a) ((int) (a).size())
  30.  
  31. #ifdef CUTEBMAING
  32. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  33. #else
  34. #define eprintf(...) 42
  35. #endif
  36.  
  37. using namespace std;
  38.  
  39. typedef long long int64;
  40. typedef long double ld;
  41. typedef unsigned long long lint;
  42.  
  43. const int inf = (1 << 30) - 1;
  44. const int64 linf = (1ll << 62) - 1;
  45. const int N = 1e5 + 100;
  46. const int K = 17;
  47.  
  48. struct layer {
  49. 	int color[N], root[N];
  50. 	int dist[N];
  51. 	pair<int, int> max1[N], max2[N];
  52.  
  53. 	layer() {
  54. 		fill_n(color, N, -1);
  55. 		fill_n(root, N, -1);
  56. 		fill_n(dist, N, -1);
  57. 		fill_n(max1, N, mp(-inf, -inf));
  58. 		fill_n(max2, N, mp(-inf, -inf));
  59. 	}
  60. };
  61.  
  62. int n, m;
  63. vector<vector<int>> g, backup;
  64. int reqA[N], reqB[N];
  65.  
  66. layer st[K];
  67.  
  68. int comp[N], compLen = 0;
  69. int parent[N], size[N];
  70.  
  71. inline void update(pair<int, int> &a, pair<int, int> &b, const pair<int, int> &c) {
  72. 	if (a.fs < c.fs) {
  73. 		if (a.sc != c.sc) {
  74. 			b = a;
  75. 		}
  76. 		a = c;
  77. 	} else if (b.fs < c.fs && c.sc != a.sc) {
  78. 		b = c;
  79. 	}
  80. }
  81.  
  82. inline void update(int v, int value) {
  83. 	for (int i = 0; i < K; i++) {
  84. 		layer &layer = st[i];
  85. 		int root = layer.root[v];
  86. 		if (root == -1) {
  87. 			break;
  88. 		}
  89. 		update(layer.max1[root], layer.max2[root], mp(value + layer.dist[v], layer.color[v]));
  90. 	}
  91. }
  92.  
  93. inline int getValue(int v) {
  94. 	int ans = -inf;
  95. 	for (int i = 0; i < K; i++) {
  96. 		layer &layer = st[i];
  97. 		int root = layer.root[v];
  98. 		if (root == -1) {
  99. 			break;
  100. 		}
  101. 		if (layer.max1[root].sc != layer.color[v] || layer.max1[root].sc == -1) {
  102. 			ans = max(ans, layer.max1[root].fs + layer.dist[v]);
  103. 		} else if (layer.max2[root].sc != layer.color[v] || layer.max2[root].sc == -1) {
  104. 			ans = max(ans, layer.max2[root].fs + layer.dist[v]);
  105. 		}
  106. 	}
  107. 	return ans;
  108. }
  109.  
  110. inline int dfsSize(int v, int p = -1) {
  111. 	size[v] = 1;
  112. 	comp[compLen++] = v;
  113. 	parent[v] = p;
  114. 	for (int to : g[v]) {
  115. 		if (to != p) {
  116. 			size[v] += dfsSize(to, v);
  117. 		}
  118. 	}
  119. 	return size[v];
  120. }
  121.  
  122. inline int findRoot(int v) {
  123. 	compLen = 0;
  124. 	int total = dfsSize(v);
  125. 	for (int i = 0; i < compLen; i++) {
  126. 		v = comp[i];
  127. 		bool flag = true;
  128. 		if ((total - size[v]) * 2 > total) {
  129. 			continue;
  130. 		}
  131. 		for (int j : g[v]) {
  132. 			if (j != parent[v] && size[j] * 2 > total) {
  133. 				flag = false;
  134. 				break;
  135. 			}
  136. 		}
  137. 		if (flag) {
  138. 			return v;
  139. 		}
  140. 	}
  141. 	assert(false);
  142. }
  143.  
  144. inline void dfsColor(layer &layer, int v, int root, int color, int d = 1, int p = -1) {
  145. 	layer.color[v] = color;
  146. 	layer.root[v] = root;
  147. 	layer.dist[v] = d;
  148. 	for (int to : g[v]) {
  149. 		if (to != p) {
  150. 			dfsColor(layer, to, root, color, d + 1, v);
  151. 		}
  152. 	}
  153. }
  154.  
  155. inline void buildDivideAndConquer(int x, int v) {
  156. 	layer &layer = st[x];
  157. 	v = findRoot(v);
  158. 	for (int to : g[v]) {
  159. 		g[to].erase(find(all(g[to]), v));
  160. 	}
  161. 	layer.color[v] = -1;
  162. 	layer.root[v] = v;
  163. 	layer.dist[v] = 0;
  164. 	for (int to : g[v]) {
  165. 		dfsColor(layer, to, v, to);
  166. 	}
  167. 	for (int to : g[v]) {
  168. 		buildDivideAndConquer(x + 1, to);
  169. 	}
  170. }
  171.  
  172. int ans = -inf;
  173.  
  174. int color[N], dist[N];
  175.  
  176. inline void dfsColor2(int v, int c, int d = 1, int p = -1) {
  177. 	color[v] = c;
  178. 	dist[v] = d;
  179. 	for (int to : g[v]) {
  180. 		if (to != p) {
  181. 			dfsColor2(to, c, d + 1, v);
  182. 		}
  183. 	}
  184. }
  185.  
  186. inline void clearUpdate(int v) {
  187. 	for (int i = 0; i < K; i++) {
  188. 		if (st[i].root[v] == -1) {
  189. 			break;
  190. 		}
  191. 		st[i].max1[st[i].root[v]].fs = -inf;
  192. 		st[i].max2[st[i].root[v]].fs = -inf;
  193. 	}
  194. }
  195.  
  196. inline void divideAndConquer(int v, vector<int> requests) {
  197. 	v = findRoot(v);
  198. 	for (int to : g[v]) {
  199. 		g[to].erase(find(all(g[to]), v));
  200. 	}
  201. 	color[v] = -1, dist[v] = 0;
  202. 	for (int i = 0; i < len(g[v]); i++) {
  203. 		int to = g[v][i];
  204. 		dfsColor2(to, i);
  205. 	}
  206. 	vector<vector<int>> req(len(g[v]));
  207. 	for (int i : requests) {
  208. 		if (reqA[i] == v) {
  209. 			ans = max(ans, getValue(reqB[i]));
  210. 			update(reqB[i], 0);
  211. 		} else {
  212. 			req[color[reqA[i]]].pb(i);
  213. 		}
  214. 	}
  215. 	for (const auto &subtree : req) {
  216. 		for (int j : subtree) {
  217. 			ans = max(ans, getValue(reqB[j]) + dist[reqA[j]]);
  218. 		}
  219. 		for (int j : subtree) {
  220. 			update(reqB[j], dist[reqA[j]]);
  221. 		}
  222. 	}
  223. 	for (int i : requests) {
  224. 		clearUpdate(reqB[i]);
  225. 	}
  226. 	for (int i = 0; i < len(g[v]); i++) {
  227. 		int to = g[v][i];
  228. 		divideAndConquer(to, req[i]);
  229. 	}
  230. }
  231.  
  232. int main() {
  233. 	cerr << sizeof(st) / 1024 / 1024 << endl;
  234. 	cin >> n >> m;
  235. 	g.resize(n);
  236. 	for (int i = 0; i < n - 1; i++) {
  237. 		int u, v; scanf("%d%d", &u, &v), u--, v--;
  238. 		g[u].pb(v);
  239. 		g[v].pb(u);
  240. 	}
  241. 	backup = g;
  242. 	for (int i = 0; i < m; i++) {
  243. 		scanf("%d%d", &reqA[i], &reqB[i]), reqA[i]--, reqB[i]--;
  244. 	}
  245. 	buildDivideAndConquer(0, 0);
  246. 	g = backup;
  247. 	vector<int> req(m);
  248. 	for (int i = 0; i < m; i++) {
  249. 		req[i] = i;
  250. 	}
  251. 	divideAndConquer(0, req);
  252. 	eprintf("ans = %d\n", ans);
  253. 	printf("%d\n", ans);
  254.     return 0;
  255. }
  256.  
Success #stdin #stdout #stderr 0.01s 52760KB
comments (?)
stdin
copy 
7 2
1 2
2 3
3 4
4 5
5 6
6 7
1 5
3 7
stdout
copy 
4
stderr
copy 
45
https://ideone.com/oHTqL8
language:
C++14 (gcc 8.3)
created:
8 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!