fork download
  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
stdin
4
2 4
4 1
3 1
stdout
2