// メモ化再帰 #include using namespace std; vector> adj; unordered_map> memo[200100]; // 木DPを行う pair rec(int r, int par = -1) { if (memo[r][par] != pair{0, 0}) return memo[r][par]; int ret0 = 0; int ret1 = 1; for (auto &&c : adj[r]) { if (c == par) continue; auto [dp0, dp1] = rec(c, r); ret0 += max(dp0, dp1); ret1 += dp0; } return memo[r][par] = {ret0, ret1}; } int main() { int N; cin >> N; adj.resize(N); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } int ans = numeric_limits::max(); for (int r = 0; r < N; r++) { auto [dp0, dp1] = rec(r); ans = min(ans, dp1); } cout << ans << endl; }