fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define ull unsigned long long
  5. #define si(X) scanf("%d", &(X))
  6. #define sll(X) scanf("%lld",&(X))
  7. #define INFL 0x3f3f3f3f3f3f3f3fLL
  8.  
  9. /* -------Template ends here-------- */
  10.  
  11. const int M = 100009;
  12. vector<int> vec[M];
  13. int dp[M][2];
  14.  
  15. void dfs(int u , int p){
  16.  
  17.     dp[u][1] = 1;
  18.  
  19.     for(int i = 0 ; i<vec[u].size() ; i++){
  20.         int v = vec[u][i];
  21.         if(v == p)
  22.             continue;
  23.         dfs(v , u);
  24.         dp[u][1] += (min(dp[v][0] , dp[v][1]));
  25.         dp[u][0] += (dp[v][1]);
  26.     }
  27.  
  28. }
  29. int main(){
  30.     //freopen("input.txt", "rt", stdin);
  31.     //freopen("output.txt", "wt", stdout);
  32.  
  33.     int n;
  34.     si(n);
  35.  
  36.     for(int i = 1 ; i<n ; i++){
  37.         int u , v;
  38.         si(u);  si(v);
  39.         vec[u].push_back(v);
  40.         vec[v].push_back(u);
  41.     }
  42.     dfs(1 , 0);
  43.     int ans = min(dp[1][0] , dp[1][1]);
  44.     // ans = max(ans , 1);
  45.     cout<<ans;
  46.  
  47. }
  48.  
Runtime error #stdin #stdout 0s 5744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/wX8oaP
problem PT07X, based on SPOJ submission 24728975 (CPP14), 2019-10-30 17:25:02
language:
C++14 (gcc 8.3)
created:
4 years 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!