Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma comment(linker, "/stack:200000000")
- //#pragma GCC optimize("O3")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- #include <bits/stdc++.h>
- #define rr resize
- #define sz size()
- #define fs first
- #define sd second
- #define mp make_pair
- #define pb push_back
- #define all(x) begin(x), end(x)
- #define OUT(x) { cout << (x); exit(0); }
- #define int ll
- using namespace std;
- typedef double db;
- typedef long long ll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef pair<int, int> pii;
- typedef vector<pii> vpii;
- const db eps = 1e-9;
- const db pi = acos(-1.0);
- const db dinf = 1e250;
- const ll INF = (ll)(2e18);
- const int inf = (int)(1e9 + 7);
- int n;
- vvi g;
- vi s;
- vi res;
- void dfs(int v, int p, int d)
- {
- res[0] += d;
- for (auto& it : g[v])
- {
- if (it == p) continue;
- dfs(it, v, d + 1);
- s[v] += s[it];
- }
- }
- void dfs1(int v, int p)
- {
- for (auto& it : g[v])
- {
- if (it == p) continue;
- res[it] = res[v] - s[it] + n - s[it];
- dfs1(it, v);
- }
- }
- int32_t main()
- {
- ios_base::sync_with_stdio(0);
- cout << fixed << setprecision(10);
- cin.tie(0);
- #ifdef _MY
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cin >> n;
- g.rr(n);
- s.rr(n, 1);
- res.rr(n, 0);
- for (int i = 0; i < n - 1; ++i)
- {
- int f, t;
- cin >> f >> t;
- --f; --t;
- g[f].pb(t);
- g[t].pb(f);
- }
- dfs(0, 0, 0);
- dfs1(0, 0);
- int minn = INF;
- for (auto& it : res) minn = min(minn, it);
- int cnt = 0;
- vi verts;
- for (int i = 0; i < n; ++i)
- {
- if (res[i] == minn)
- {
- ++cnt;
- verts.pb(i + 1);
- }
- }
- cout << minn << " " << cnt << " ";
- for (auto& it : verts) cout << it << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement