Advertisement
Guest User

Untitled

a guest
Apr 21st, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.89 KB | None | 0 0
  1. //#pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("O3")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #include <bits/stdc++.h>
  5. #define rr resize
  6. #define sz size()
  7. #define fs first
  8. #define sd second
  9. #define mp make_pair
  10. #define pb push_back
  11. #define all(x) begin(x), end(x)
  12. #define OUT(x) { cout << (x); exit(0); }
  13. #define int ll
  14. using namespace std;
  15. typedef double db;
  16. typedef long long ll;
  17. typedef vector<int> vi;
  18. typedef vector<vi> vvi;
  19. typedef pair<int, int> pii;
  20. typedef vector<pii> vpii;
  21. const db eps = 1e-9;
  22. const db pi = acos(-1.0);
  23. const db dinf = 1e250;
  24. const ll INF = (ll)(2e18);
  25. const int inf = (int)(1e9 + 7);
  26.  
  27. int n;
  28. vvi g;
  29.  
  30. vi s;
  31. vi res;
  32.  
  33. void dfs(int v, int p, int d)
  34. {
  35. res[0] += d;
  36. for (auto& it : g[v])
  37. {
  38. if (it == p) continue;
  39. dfs(it, v, d + 1);
  40. s[v] += s[it];
  41. }
  42. }
  43.  
  44. void dfs1(int v, int p)
  45. {
  46. for (auto& it : g[v])
  47. {
  48. if (it == p) continue;
  49. res[it] = res[v] - s[it] + n - s[it];
  50. dfs1(it, v);
  51. }
  52. }
  53.  
  54. int32_t main()
  55. {
  56. ios_base::sync_with_stdio(0);
  57. cout << fixed << setprecision(10);
  58. cin.tie(0);
  59.  
  60. #ifdef _MY
  61. freopen("input.txt", "r", stdin);
  62. freopen("output.txt", "w", stdout);
  63. #endif
  64.  
  65. cin >> n;
  66.  
  67. g.rr(n);
  68. s.rr(n, 1);
  69. res.rr(n, 0);
  70.  
  71. for (int i = 0; i < n - 1; ++i)
  72. {
  73. int f, t;
  74. cin >> f >> t;
  75. --f; --t;
  76. g[f].pb(t);
  77. g[t].pb(f);
  78. }
  79.  
  80. dfs(0, 0, 0);
  81. dfs1(0, 0);
  82.  
  83. int minn = INF;
  84. for (auto& it : res) minn = min(minn, it);
  85.  
  86. int cnt = 0;
  87. vi verts;
  88. for (int i = 0; i < n; ++i)
  89. {
  90. if (res[i] == minn)
  91. {
  92. ++cnt;
  93. verts.pb(i + 1);
  94. }
  95. }
  96.  
  97. cout << minn << " " << cnt << " ";
  98. for (auto& it : verts) cout << it << " ";
  99.  
  100. return 0;
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement