#include #include #include #include namespace nono { template struct EdgeBase { int from; int to; T weight; EdgeBase() {} EdgeBase(int from, int to, T weight = 1): from(from), to(to), weight(weight) {} }; using Edge = EdgeBase; template using WeightedEdge = EdgeBase; template class Graph { struct Edge_ { int to; T weight; int id; }; using iterator = std::vector::iterator; using const_iterator = std::vector::const_iterator; using subrange = std::ranges::subrange; using const_subrange = std::ranges::subrange; public: template friend Graph to_undirected_graph(int n, const std::vector>& edges); template friend Graph to_directed_graph(int n, const std::vector>& edges); subrange operator[](int i) { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } const_subrange operator[](int i) const { return std::ranges::subrange(edges_.begin() + indptr_[i], edges_.begin() + indptr_[i + 1]); } int size() const { return n_; } int edge_size() const { return m_; } bool is_directed() const { return directed_; } bool is_undirected() const { return !is_directed(); } private: Graph(int n, const std::vector>& edges, bool directed) : n_(n), m_(edges.size()), indptr_(n_ + 1), edges_(directed ? edges.size() : 2 * edges.size()), directed_(directed) { for (const auto& e: edges) { indptr_[e.from + 1]++; if (!directed_) indptr_[e.to + 1]++; } for (int i = 0; i < n_; i++) { indptr_[i + 1] += indptr_[i]; } auto index = indptr_; for (int i = 0; i < std::ssize(edges); i++) { const auto& e = edges[i]; edges_[index[e.from]++] = Edge_(e.to, e.weight, i); if (!directed_) edges_[index[e.to]++] = Edge_(e.from, e.weight, i); } } int n_; int m_; std::vector indptr_; std::vector edges_; bool directed_; }; template Graph to_undirected_graph(int n, const std::vector>& edges) { return Graph(n, edges, false); } template Graph to_directed_graph(int n, const std::vector>& edges) { return Graph(n, edges, true); } } // namespace nono namespace nono { void solve() { int n; std::cin >> n; std::vector edges; for (int i = 0; i + 1 < n; i++) { int u, v; std::cin >> u >> v; u--; v--; edges.emplace_back(u, v); } auto graph = to_undirected_graph(n, edges); std::vector bdp(n); std::vector wdp(n); { auto dfs = [&](auto self, int u, int p) -> void { bdp[u] = 1; wdp[u] = 0; for (auto e: graph[u]) { if (e.to == p) continue; self(self, e.to, u); bdp[u] += wdp[e.to]; wdp[u] += bdp[e.to]; } }; dfs(dfs, 0, -1); } int ans = 1e9; { auto dfs = [&](auto self, int u, int p, int pwv, int pbv) -> void { int black = 1; for (auto e: graph[u]) { if (e.to == p) { black += pwv; } else { black += wdp[e.to]; } } ans = std::min(ans, black); int white = 0; for (auto e: graph[u]) { if (e.to == p) { white += pbv; } else { white += bdp[e.to]; } } for (auto e: graph[u]) { if (e.to == p) continue; self(self, e.to, u, white - bdp[e.to], black - wdp[e.to]); } }; dfs(dfs, 0, -1, 0, 0); } std::cout << ans << '\n'; } } // namespace nono int main() { std::cin.tie(0)->sync_with_stdio(0); std::cout << std::fixed << std::setprecision(16); int t = 1; while (t--) nono::solve(); }