sacgajcvs

Untitled

Oct 22nd, 2020
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 100005
  4.  
  5. vector<int> a[N];
  6. int dis[N];
  7. int ans[N];
  8. bool vis[N];
  9.  
  10. void fun(int node) {
  11. vis[node] = 1;
  12. dis[node] = N;
  13. for(auto i : a[node]) {
  14. if(!vis[i]) {
  15. fun(i);
  16. dis[node] = min(dis[i] + 1, dis[node]);
  17. }
  18. }
  19. if(dis[node] == N) {
  20. dis[node] = 1;
  21. }
  22. }
  23.  
  24. void fun2(int node, int pre) {
  25. // cout << node << " - " << pre << endl;
  26. vis[node] = 1;
  27. vector<pair<int,int>> tmp;
  28. if(node != 1 || a[node].size() == 1) {
  29. tmp.push_back({pre, -1});
  30. }
  31. bool f = 0;
  32. for(auto i : a[node]) {
  33. if(!vis[i]) {
  34. tmp.push_back({dis[i], i});
  35. f = 1;
  36. }
  37. }
  38. if(!f) {
  39. tmp.push_back({0,-2});
  40. }
  41. sort(tmp.begin(),tmp.end());
  42. auto calc = [&] (vector<int> vvv) {
  43. set<int> st;
  44. for(auto i : vvv) {
  45. st.insert(i);
  46. }
  47. for(auto i : tmp) {
  48. if(st.find(i.second) == st.end()) {
  49. return i.first;
  50. }
  51. }
  52. return 0;
  53. };
  54. for(auto i : a[node]) {
  55. if(!vis[i]) {
  56. fun2(i, calc({i}) + 1);
  57. }
  58. }
  59. ans[node] = tmp[0].first + 1;
  60. }
  61.  
  62.  
  63. void solve()
  64. {
  65. int n, x, y;
  66. cin >> n;
  67. for(int i = 0; i < n - 1; i++) {
  68. cin >> x >> y;
  69. a[x].push_back(y);
  70. a[y].push_back(x);
  71. }
  72. fun(1);
  73. memset(vis, false, sizeof(bool) * (n + 1));
  74. fun2(1, 0);
  75. int mx = -1, ps = 0;
  76. for(int i = 1; i <= n; i++) {
  77. if(ans[i] > mx) {
  78. mx = ans[i];
  79. ps = i;
  80. }
  81. }
  82. // for(int i = 1; i <= n; i++) {
  83. // cout << i << " -> " << dis[i] << " " << ans[i] << endl;
  84. // }
  85. cout << ps << " " << mx << endl;
  86. return;
  87. }
  88. int main()
  89. {
  90. int TESTS=1;
  91. // cin>>TESTS;
  92. while(TESTS--)
  93. {
  94. solve();
  95. }
  96. return 0;
  97. }
Advertisement
Add Comment
Please, Sign In to add comment