Untitled
user_5668965
c_cpp
a year ago
1.4 kB
7
Indexable
#pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("ssse3,sse4,popcnt,lzcnt,abm,bmi,bmi2,mmx,avx2,fma") #include <bits/stdc++.h> using namespace std; typedef long long ll; ll MOD = 998244353; ll mod = 1e9+7; double eps = 1e-3; double ep = 1e-8; #define rep(i, n) for(ll i = 0, _n = (ll)(n); i < _n; i++) #define endl '\n' //comment out for interactive problems vector<pair<ll,ll>> adj[200005]; vector<ll> cnt(200005,0); ll maxc = 0, c = 0; void dfs(ll u, ll p, ll d){ cnt[u] = d; maxc = max(maxc,d); for(auto v: adj[u]){ if(v.first!=p){ dfs(v.first,u,d+v.second); if (v.second == 1) c++; } } } void solve(){ ll n; cin>>n; rep(i,n-1){ ll u,v; cin>>u>>v; adj[u].push_back({v,-1}); adj[v].push_back({u,1}); } dfs(1,0,0); vector<ll> ans; rep(i,n){ if(cnt[i+1]==maxc){ ans.push_back(i+1); } } cout<<c - maxc<<endl; rep(i,ans.size()){ cout<<ans[i]<<" "; } } int main(){ //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); ll t=1; //cin>>t; for (ll i=1; i<=t; i++){ //cout<<"Case #"<<i<<": "; solve(); } return 0; }
Editor is loading...
Leave a Comment