fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define INF 1000000007
  4. #define EPS 0.000001
  5. #define f first
  6. #define s second
  7. #define in(n) scanf("%lld", &n)
  8. #define ina(arr,n) for(ll x = 0; x < n; x++) in(arr[x]);
  9. #define loop(i,n) for(ll i=0;i<n;i++)
  10. #define leep(i,n) for(ll i=1;i<=n;i++)
  11. using namespace std;
  12.  
  13. vector <ll>vec[112345];
  14. ll dp[112345];
  15.  
  16. void dfs(ll node,ll parent){
  17.     for(auto x:vec[node]){
  18.         if(x!=parent){
  19.             dfs(x,node);
  20.             dp[node]+=dp[x];
  21.         }
  22.     }
  23.     dp[node]++;
  24. }
  25.  
  26. int main(){
  27.     ll node,edge;
  28.     cin>>node;
  29.     edge=node-1;
  30.     loop(i,(node-1)){
  31.         ll x,y;
  32.         in(x);
  33.         in(y);
  34.         vec[x].push_back(y);
  35.         vec[y].push_back(x);
  36.     }
  37.     ll leaf=0;
  38.     for(ll i=1;i<=node;i++){
  39.         if(vec[i].size()==1){
  40.             leaf=i;
  41.             break;
  42.         }
  43.     }
  44.     dfs(1,-1);
  45.     ll ans=0;
  46.     for(ll i=1;i<=node;i++){
  47.         if(!(dp[i]&1)&&(vec[i].size()!=1)){
  48.             ans++;
  49.         }
  50.     }
  51.     if(node%2==0)
  52.         cout<<ans<<endl;
  53.     else
  54.         cout<<-1<<endl;
  55.     return 0;
  56. }
Success #stdin #stdout 0s 5836KB
comments (?)
stdin
copy 
4
2 4
4 1
3 1
stdout
copy 
2
https://ideone.com/hoqWtg
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!