Advertisement
Guest User

Untitled

a guest
Feb 19th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <stack>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <cmath>
  8. #include <set>
  9. #include <map>
  10.  
  11. using namespace std;
  12.  
  13. vector<int> g[223456];
  14.  
  15. int dist[223456];
  16. int dist2[223456];
  17.  
  18. void dfs(int v, int p = -1)
  19. {
  20. for(int i = 0; i < g[v].size(); ++i)
  21. {
  22. int to = g[v][i];
  23. if (to == p)
  24. continue;
  25. dfs(to, v);
  26. }
  27. }
  28.  
  29. void dfsWithDist(int v, int p = -1)
  30. {
  31. for(int i = 0; i < g[v].size(); ++i)
  32. {
  33. int to = g[v][i];
  34. if (to == p)
  35. continue;
  36. dist[to] = dist[v] + 1;
  37. dfsWithDist(to, v);
  38. }
  39. }
  40.  
  41. void dfsWithDist2(int v, int p = -1)
  42. {
  43. for(int i = 0; i < g[v].size(); ++i)
  44. {
  45. int to = g[v][i];
  46. if (to == p)
  47. continue;
  48. dist2[to] = dist2[v] + 1;
  49. dfsWithDist2(to, v);
  50. }
  51. }
  52.  
  53. bool dfsWithPath(int v, int u, vector<int>& path, int p = -1)
  54. {
  55. path.push_back(v);
  56. if (v == u)
  57. return true;
  58. for(int i = 0; i < g[v].size(); ++i)
  59. {
  60. int to = g[v][i];
  61. if (to == p)
  62. continue;
  63. if (dfsWithPath(to, u, path, v))
  64. return true;
  65. }
  66. path.pop_back();
  67. }
  68.  
  69. bool used[223456];
  70.  
  71. int distLast[223456];
  72. int mx;
  73. void dfsWithUsedAndDist(int v)
  74. {
  75. used[v] = 1;
  76. for(int i = 0; i < g[v].size(); ++i)
  77. {
  78. int to = g[v][i];
  79. if (used[to])
  80. continue;
  81. distLast[to] = distLast[v] + 1;
  82. mx = max(mx, distLast[to]);
  83. dfsWithUsedAndDist(to);
  84. }
  85. }
  86.  
  87. int longestPath[223456];
  88.  
  89. bool ok(vector<int>&path, int d, int m) {
  90. int l = m;
  91. int r = d - m - 1;
  92. if ((r-l) / 2 > m)
  93. return false;
  94. for(int i = 0; i < path.size(); ++i) {
  95. int mn = 1e9;
  96. mn = min(mn, longestPath[path[i]] + abs(l-i));
  97. mn = min(mn, longestPath[path[i]] + abs(r-i));
  98. if (mn > m)
  99. return false;
  100. }
  101. return true;
  102. }
  103.  
  104. int main()
  105. {
  106. int n;
  107. cin >> n;
  108. for(int i = 0; i < n-1; ++i)
  109. {
  110. int u, v;
  111. cin >> u >> v;
  112. g[v].push_back(u);
  113. g[u].push_back(v);
  114. }
  115.  
  116. dfsWithDist(1);
  117. int ind = max_element(dist + 1, dist + n + 1) - dist;
  118.  
  119. dfsWithDist2(ind);
  120.  
  121. int ind2 = max_element(dist2 + 1, dist2 + n + 1) - dist2;
  122. vector<int> path;
  123. dfsWithPath(ind, ind2, path);
  124. // for(int i = 0; i < path.size(); ++i)
  125. // cout << path[i] << " ";
  126. // cout << endl;
  127.  
  128. int d = path.size();
  129.  
  130. for(int i = 0; i < path.size(); ++i)
  131. used[path[i]] = 1;
  132.  
  133. for(int i = 0; i < path.size(); ++i) {
  134. mx = 0;
  135. dfsWithUsedAndDist(path[i]);
  136. longestPath[path[i]] = mx;
  137. }
  138.  
  139. for(int i = 1; i <= n; ++i)
  140. used[i] = 0;
  141.  
  142. for(int i = 0; i < path.size(); ++i)
  143. used[path[i]] = 1;
  144.  
  145. int l = 0;
  146. int r = d / 2 + 1;
  147. while(r-l > 1)
  148. {
  149. int m = (l+r) >> 1;
  150. if (ok(path, d, m))
  151. r = m;
  152. else
  153. l = m;
  154. }
  155. if (ok(path, d, l))
  156. r = l;
  157. if (r == d-r-1)
  158. cout << path[r] << " " << path[d-r] << endl;
  159. else
  160. cout << path[r] << " " << path[d-r-1] << endl;
  161. // int l,r;
  162. // int mxL = ((d & 1) ? d / 4 : (d-1) / 4);
  163. // int mxR = d-1 - mxL;
  164. //
  165. // if (d&1) {
  166. // mxL = max(mxL, longestPath[path[d/2]]);
  167. // mxR = min(mxR, d-1 - longestPath[path[r]]);
  168. // --l, ++r;
  169. // if (longestPath[path[d/2]] == d/2) {
  170. // cout << path[d/2] << " " << (path[d/2] == 1 ? 2 : 1) << endl;
  171. // return 0;
  172. // }
  173. // l = d/2 - 1;
  174. // r = d/2 + 1;
  175. // }
  176. // else {
  177. // l = d/2 - 1;
  178. // r = d/2;
  179. // }
  180. // while(l >= 0) {
  181. // if (d & 1) {
  182. // mxL = max(mxL, longestPath[path[l]] + l - d/2);
  183. // mxR = min(mxR, d/2 + r - longestPath[path[r]]);
  184. // } else {
  185. // mxL = max(mxL, longestPath[path[l]] + l - d/2 + 1);
  186. // mxR = min(mxR, d/2 + r - longestPath[path[r]] - 1);
  187. // }
  188. // --l, ++r;
  189. // }
  190. // cout << path[mxL] << " " << path[mxR] << endl;
  191. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement