Tree_matching.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;

vector<int> adj[maxn];
bool pareado[maxn];
int ans=0;

void dfs(int u, int p) {
	for (int v : adj[u]) if(v!=p) {
		dfs(v, u);
		if (!pareado[v] && !pareado[u])
			pareado[u]=pareado[v]=1, ans++;
	}
}

int main() {
	int n; cin >> n;
	for(int i=1; i<n; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b), adj[b].push_back(a);
	}

	dfs(1,1);

	cout << ans << '\n';
}