Link : https://cses.fi/problemset/task/1130/ My approach : 1. using dfs I going down if leaf node encounter then take it if its parent is not visited and mark both of them visited.

1. If lets all child is giving answer and if any one of the child is not visited and parent is not visited increment count by 1 and mark them visited.

#include<bits/stdc++.h>
using namespace std;


unordered_map<int,vector<int>>mp;



int dfs(int i,int prev,vector<int>&visited){
        
        if(mp[i].size()==0){
// case 1 leaf case 
           if(prev != -1 && !visited[i] && !visited[prev]){
             visited[i] = 1;
             visited[prev]= 1;
            
             return 1;
           }
          
           return 0;
        }
        int cal = 0;
        int p = -1;
        for(auto x : mp[i]){
            
            cal += dfs(x,i,visited);
           if(!visited[x]){
             p = x;
           }
        }
// case 2 for non leaf case 
        if(p != -1 && !visited[p]){
            if(!visited[i] && !visited[p]){
              cal++;
               visited[i] = 1;
               visited[p] = 1;
            }
        }
  
        return  cal;

}
void solve(){
    int n ;
    cin>>n;
 
    for(int i = 1;i<=n-1;i++){
       int a,b;
       cin>>a>>b;
      mp[a].push_back(b);
    }
    vector<int>visited(n+1,0);

   int ans = 0;
   for(int i= 1;i<=n;i++){
      int prev = -1;
      if(!visited[i]){
        ans += dfs(i,prev,visited);
      }
   }
   cout<<ans<<endl;
   
}

void template1(){
     
    int t;
    cin>>t;

    while(t>0){
        solve();
        t--;
    }
}


void template2(){
    solve();
}


int main(){
   // template1();
     template2();
    return 0;
}