fork(2) download 
  1. #include<bits/stdc++.h>
  2.  
  3. const double pi=acos(-1.0);
  4. using namespace std;
  5. #define   endl    '\n'
  6. #define   sl(n)     scanf("%lld",&n)
  7. #define   mp      make_pair
  8. #define   pb      push_back
  9. #define   ppb     pop_back
  10. #define   fi      first
  11. #define   se      second
  12. #define   ll      long long
  13. #define   ull     unsigned long long
  14. #define   ld      long double
  15. #define   pii     pair<int, int>
  16. #define   f(i,a,b)  for(ll i = (ll)(a); i < (ll)(b); i++)
  17. #define   rf(i,a,b)   for(ll i = (ll)(a); i > (ll)(b); i--)
  18. #define   ms(a,b)   memset((a),(b),sizeof(a))
  19. #define   abs(x)    ((x<0)?(-(x)):(x))
  20. #define   MAX     200005
  21. #define   inf     LLONG_MAX
  22. #define   ninf    LLONG_MIN
  23. #define   MIN     INT_MIN
  24. #define   yeet    return 0;
  25. #define tihs if(fopen("input.txt","r"))freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
  26.  
  27. #define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
  28. #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
  29.  
  30. inline long long  MAX2(long long  a, long long  b){return (a)>(b)?(a):(b);}
  31. inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
  32. inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
  33. inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
  34.  
  35.  
  36. int mod = 1e9 +7 ;
  37.  
  38.  
  39. ////****************************************************************************************************************************************************************************************************************////
  40. vector<int>adj[MAX];
  41. ll dp[MAX][2];
  42.  
  43. void dfs (int src,int par){
  44.             int leaf=1;
  45.             dp[src][1]=0;
  46.             dp[src][0]=0;
  47.  
  48.             for(auto child:adj[src]){
  49.                     if(child!=par){
  50.                         leaf=0;
  51.                          dfs(child,src);
  52.                     }
  53.             }
  54.         if(leaf==1)return ;
  55.  
  56.         for(auto child:adj[src]){
  57.                if(child!=par){
  58.                dp[src][0]+=MAX2(dp[child][0],dp[child][1]);
  59.  
  60.                }
  61.         }
  62.  
  63.         for(auto child:adj[src]){
  64.             if(child!=par) {
  65.                  dp[src][1]=MAX2(dp[src][1],1+ dp[child][0]+( dp[src][0]-MAX2(dp[child][0],dp[child][1])));
  66.         }
  67.         }
  68.  
  69.       }
  70.  
  71.  int main(){
  72.      tihs;
  73.      int n;
  74.      cin>>n;
  75.      for(int i=0;i<n-1;i++){
  76.         int ss,ee;
  77.         cin>>ss>>ee;
  78.         adj[ss].pb(ee);
  79.         adj[ee].pb(ss);
  80.      }
  81.      dfs(1,0);
  82.      cout<<MAX2(dp[1][0],dp[1][1])<<endl;
  83.      }
  84.  
  85.  
Success #stdin #stdout 0s 8200KB
comments (?)
stdin 
10
5 8
4 6
9 1
10 4
1 3
2 3
7 9
6 2
5 10
stdout 
5
https://ideone.com/AkuUN5
language:
C++14 (gcc 8.3)
created:
5 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!