fork download
copy 
  1. // Author: Amey Bhavsar - ameybhavsar24@(github & twitter)
  2. // IDE: Geany on Ubuntu 20.04
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. typedef long long ll;
  6. #define rep(i,a,b) for(auto i=a;i<b;i++)
  7. #define repD(i,a,b) for(auto i=a;i>=b;i--)
  8. #define pb push_back
  9. #define mp make_pair
  10. #define ff first
  11. #define ss second
  12. #define all(x) (x).begin(), (x).end()
  13. #define rall(x) (x).rbegin, (x).rend()
  14. #define MOD 1000000007
  15. int main() {
  16.   ios_base::sync_with_stdio(false);cin.tie(NULL);
  17.   int n;
  18.   cin >> n;
  19.   vector< vector< int > > adj(n+1);
  20.   rep(i,0,n-1) {
  21.     int a, b;
  22.     cin >> a >> b;
  23.     adj[a].pb(b);
  24.     adj[b].pb(a);
  25.   }
  26. vector<bool> taken(n+1);
  27. taken[0] = true;
  28. function<void(int,int)> dfs = [&] (int u, int pu) {
  29.   for (auto& v:adj[u]) {
  30.     if (v != pu) {
  31.       dfs(v, u);
  32.     }
  33.   }
  34.   if (!taken[u] && !taken[pu]) {
  35.     taken[u] = true;
  36.     taken[pu] = true;
  37.   }
  38. };
  39. dfs(1,0);
  40. int cnt = count_if(all(taken),[&](bool e){return e == true;});
  41. cout << (cnt - 1)/2;
  42.   return 0;
  43. }
  44.  
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
5
1 2
1 3
3 4
3 5
stdout
copy 
2
https://ideone.com/fLqs9y
language:
C++14 (gcc 8.3)
created:
2 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!