Advertisement
Guest User

Untitled

a guest
Dec 18th, 2018
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n,m,a,b,v;
  4. #define MAXN 1000069
  5. int syny[MAXN];
  6. int fath[MAXN];
  7. long long sumDown[MAXN];
  8. long long mainDist[MAXN];
  9. int deg[MAXN];
  10.  
  11. void DFS (int node, vector <vector <int> > &G, vector <bool> &V)
  12. {
  13. V[node] = true;
  14. for (auto nei:G[node]) if (V[nei] == false)
  15. {
  16. fath[nei] = node;
  17. DFS(nei, G, V);
  18. }
  19. }
  20.  
  21. void DFS_Ans (int node, vector <vector <int> > &G, vector <bool> &V)
  22. {
  23. V[node] = true;
  24. for (auto nei:G[node]) if (V[nei] == false)
  25. {
  26. if (fath[nei] != -1)
  27. {
  28. mainDist[nei] = mainDist[node] + n - 2*syny[nei];
  29. }
  30. DFS_Ans(nei, G, V);
  31. }
  32. }
  33.  
  34. int main()
  35. {
  36. ios_base::sync_with_stdio(0);
  37. cin.tie(0);
  38. cout.tie(0);
  39. for (int i=0; i!=MAXN; ++i)
  40. {
  41. syny[i] = 1;
  42. fath[i] = -1;
  43. sumDown[i] = 0;
  44. mainDist[i] = 0;
  45. deg[i] = 0;
  46. }
  47.  
  48. cin >> n;
  49. m = n - 1;
  50. vector <vector <int> > Graph(n);
  51. while (m--)
  52. {
  53. cin >> a >> b;
  54. a--,--b;
  55. Graph.at(a).push_back(b);
  56. Graph.at(b).push_back(a);
  57. deg[a]++;
  58. deg[b]++;
  59. }
  60.  
  61. vector <bool> Vis(n, false);
  62. DFS(0, Graph, Vis);
  63.  
  64. queue <int> Q;
  65. for (int i=1; i!=n; ++i) if (deg[i] == 1) Q.push(i), sumDown[i] = 0;
  66. vector <int> TopOrd;
  67. while (Q.size())
  68. {
  69. v = Q.front();
  70. Q.pop();
  71. TopOrd.push_back(v);
  72. if (fath[v] == -1) continue;
  73. deg[fath[v]]--;
  74. if (deg[fath[v]] < 2) Q.push(fath[v]);
  75. }
  76.  
  77. for (auto node:TopOrd)
  78. {
  79. for (auto nei:Graph[node]) if (nei != fath[node]) syny[node] += syny[nei], sumDown[node] += sumDown[nei] + syny[nei];
  80. // cout << syny[node] << ", " << sumDown[node] << endl;
  81. }
  82.  
  83. mainDist[0] = sumDown[0];
  84. for (int i=0; i!=n; ++i) Vis[i] = false;
  85. DFS_Ans(0, Graph, Vis);
  86. //for (int i=0; i!=n; ++i) cout << mainDist[i] << " ";
  87.  
  88. long long mV = -1;
  89. for (int i=0; i!=n; ++i) mV = max(mV, mainDist[i]);
  90. for (int i=0; i!=n; ++i)
  91. {
  92. if (mV == mainDist[i])
  93. {
  94. cout << i + 1;
  95. return 0;
  96. }
  97. }
  98.  
  99. return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement