Advertisement
Guest User

Untitled

a guest
Oct 20th, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <map>
  4. #include <vector>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <cstring>
  8. #include <queue>
  9.  
  10. #define ll long long
  11. #define ld double
  12. #define pb push_back
  13. #define ft first
  14. #define sd second
  15. #define inf ((ll)1e17)
  16.  
  17. #define mod (1e9+7)
  18. #define eps (-1e7)
  19.  
  20. using namespace std;
  21.  
  22. vector <ll> g[600000];
  23. ll dup[600000],d[600000],p[600000];
  24. bool u1[600000],u2[600000];
  25.  
  26. void dfs1(ll v) {
  27. u1[v] = 1;
  28. ll kol = 0;
  29.  
  30. for (auto to: g[v]) {
  31. if (!u1[to]) {
  32. p[to] = v;
  33. dfs1(to);
  34. d[v] = max(d[v],d[to]);
  35. kol++;
  36. }
  37. }
  38. if (kol != 0)
  39. d[v]++;
  40. }
  41.  
  42. void dfs2(ll v,ll mx=0) {
  43. u2[v] = 1;
  44. dup[v] = max(dup[v],mx);
  45.  
  46. vector <ll> ver;
  47. for (auto to: g[v]) {
  48. if (!u2[to]) {
  49. ver.pb(to);
  50. }
  51. }
  52.  
  53. vector <ll> mpref(ver.size()+1),msuff(ver.size()+1);
  54. for (ll i = 0; i < ver.size(); i++) {
  55. if (i==0) {
  56. mpref[i] = d[ver[i]]+1;
  57. }
  58. else {
  59. mpref[i] = max(mpref[i-1],d[ver[i]]+1);
  60. }
  61. }
  62.  
  63. for (ll i = (ll)ver.size()-1; i >= 0; i--) {
  64. if (i == (ll)ver.size()-1) {
  65. msuff[i] = d[ver[i]]+1;
  66. }
  67. else {
  68. msuff[i] = max(msuff[i+1],d[ver[i]]+1);
  69. }
  70. }
  71.  
  72. ll ind = 0;
  73. for (auto to: g[v]) {
  74. if (!u2[to]) {
  75. dup[to] = dup[v]+1;
  76. ll k1 = 0;
  77. if (ind > 0)
  78. k1 = mpref[ind-1];
  79.  
  80. ll k2 = 0;
  81.  
  82. if (ind+1<ver.size())
  83. k2 = msuff[ind+1];
  84.  
  85. dfs2(to,max(k1,k2)+1);
  86. ind++;
  87. }
  88. }
  89. }
  90.  
  91. int main() {
  92.  
  93. ios::sync_with_stdio(0);
  94. cin.tie();
  95. cout.tie();
  96.  
  97. //freopen("c.in","r",stdin);
  98. //freopen("c.out","w",stdout);
  99.  
  100. ll n;
  101.  
  102. cin >> n;
  103.  
  104. for (ll i = 1; i < n; i++) {
  105. ll a ,b;
  106.  
  107. cin >> a >> b;
  108.  
  109. g[a].pb(b);
  110. g[b].pb(a);
  111. }
  112.  
  113.  
  114. p[1] = 1;
  115. dfs1(1);
  116. dfs2(1);
  117.  
  118. ll ans = inf;
  119. ll ver = 0;
  120. for (ll i = 1; i <= n; i++) {
  121. ll cur = 0;
  122. for (auto x: g[i]) {
  123. if (x != p[i]) {
  124. cur += (d[x] + 1) * (d[x] + 1);
  125. }
  126. }
  127.  
  128. ll mn = dup[i]-1;
  129.  
  130. cur += (mn+1)*(mn+1);
  131. if (ans > cur) {
  132. ans = cur;
  133. ver = i;
  134. }
  135. }
  136.  
  137. cout << ans << ' ' << ver;
  138. return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement