fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define pii pair <int, int>
  6. #define int long long
  7. const int MAXN = 2e5+5;
  8.  
  9. int n, dp[MAXN], mini = 1e9;
  10. vector <pii> adj[MAXN];
  11.  
  12. void dfs1(int x, int pa){
  13.     for (auto i : adj[x]){
  14.         int  a = i.fi, b = i.se;
  15.  
  16.         if ( a== pa) continue;
  17.       dfs1(a, x);
  18.     dp[x] += dp[a] + b;
  19.     }
  20. }
  21.  
  22. void dfs2(int x, int pa){
  23.     for (auto i : adj[x]){
  24.         int a = i.fi, b = i.se;
  25.         if ( a == pa) continue;
  26.         // knp gak 0, karena buat i --> x mungkin 0, tp kl sebaliknya tetap
  27.         if (!b) dp[a] = dp[x] +1;
  28.         else dp[a] = dp[x]-1;
  29.        dfs2(a, x);
  30.     }
  31. }
  32.  
  33.  signed main(){
  34.      cin >> n;
  35.      for (int i =1; i <= n-1; i++){
  36.          int x, y;
  37.          cin >> x >> y ;
  38.          adj[x].push_back({y, 0});
  39.          adj[y].push_back({x, 1});
  40.      }
  41.  
  42.      dfs1(1, 0);
  43.      dfs2(1, 0);
  44.  
  45. for (int i =1; i <= n; i++){
  46. mini = min(mini, dp[i]);
  47. }
  48. cout << mini << endl;
  49. for (int i =1; i <= n;  i++){
  50. if ( dp[i] == mini){
  51. cout << i << " " ;
  52. }
  53.     }
  54.  }
Success #stdin #stdout 0.01s 8304KB
comments (?)
stdin
copy 
3
2 1
2 3
stdout
copy 
0
2
https://ideone.com/5Jdvqq
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!