fork download
  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 = 100001 + 1;
  12. //increasing M by 1
  13. vector<int> vec[M];
  14. int dp[M][2];
  15.  
  16. void dfs(int u , int p){
  17.  
  18. // dp[u][1] = 1;
  19. // no need for this
  20. int a = 0, b = 1;
  21. for(int i = 0 ; i<vec[u].size() ; i++){
  22. int v = vec[u][i];
  23. if(v == p)
  24. continue;
  25. dfs(v , u);
  26. //added new things
  27. a += dp[v][0];
  28. b += dp[v][1];
  29. // we first need to some them up and then choose the optimal to store it later
  30. // dp[u][1] += (min(dp[v][0] , dp[v][1]));
  31. }
  32. dp[u][1] = min(a, b);
  33. dp[u][0] = b;
  34. }
  35. int main(){
  36. //freopen("input.txt", "rt", stdin);
  37. //freopen("output.txt", "wt", stdout);
  38. memset(dp , 0 , sizeof(dp));
  39. int n;
  40. si(n);
  41.  
  42. for(int i = 1 ; i<n ; i++){
  43. int u , v;
  44. si(u); si(v);
  45. vec[u].push_back(v);
  46. vec[v].push_back(u);
  47. }
  48. dfs(1 , 0);
  49. int ans = min(dp[1][0] , dp[1][1]);
  50. ans = max(ans , 1);
  51. cout<<ans;
  52.  
  53. }
Success #stdin #stdout 0s 6828KB
stdin
6
1 2
2 3
3 4
4 5
5 6
stdout
3