//サンプル3のお絵描きを間違えて嵌った… //最大マッチングがそれっぽいですね(証明詰められず)。 //市松模様は多分WAじゃないかなと思うけど、反例すぐ出てこない。 #include #include using namespace std; int n; vector et[100000]; bool used[100000]; int match = 0; void dfs(int p, int v) { if (et[v].size() == 1 && p != -1) { //葉 return; } for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; dfs(v, nv); if (used[v] == false && used[nv] == false) { used[nv] = true; used[v] = true; match++; } } } signed main() { int i; cin >> n; for (i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; et[u].push_back(v); et[v].push_back(u); } dfs(-1, 0); cout << match << endl; return 0; }