#include #include #include #include #include #include // Metafunctions {{{ template auto is_valid_fn(F fn, Args... args) -> decltype( fn(args...), std::true_type{}); std::false_type is_valid_fn(...); template struct is_valid : decltype(is_valid_fn(std::declval(), std::declval()...)) {}; struct is_container_impl { template auto operator() (T t) -> decltype(std::begin(t)); }; template struct is_container : is_valid {}; template struct is_nonstring_container : std::integral_constant{} && !std::is_same{}> {}; // }}} // {{{ Dirty stuffs using ll = long long; using Z = int; #define rep(i, n) for (decltype(n) i = 0; i < (n); ++i) #define rrep(i, n) for (auto i = (n); i >= 0; --i) #define btwn(i, from, below) for (auto i = (from); i < (below); ++i) #define rbtwn(i, from, above) for (auto i = (from); i >= (above); --i) #define each(e, c) for (auto&& e : c) #define all(c) std::begin(c), std::end(c) // }}} // Range {{{ template class slice_wrapper { public: using iterator = typename Container::iterator; private: Container& entity; iterator start, last; public: slice_wrapper(Container& container, std::size_t head, std::size_t tail) : entity(container), start(std::next(std::begin(container), head)), last(std::prev(std::end(container), tail)) {} iterator begin() const { return start; } iterator end() const { return last; } }; template inline slice_wrapper slice(Container& container, std::size_t head, std::size_t tail = 0) { return slice_wrapper(container, head, tail); } // }}} // I/O utlity {{{ #define HEAD(x, ...) x #define READ_INPUT(T, ...) T HEAD(__VA_ARGS__); read_input(__VA_ARGS__) #define rz(...) READ_INPUT(Z, __VA_ARGS__) #define rint(...) READ_INPUT(int, __VA_ARGS__) #define rll(...) READ_INPUT(ll, __VA_ARGS__) #define rstr(s) READ_INPUT(std::string, s) #define RCONT_IMPL(c, ...) c; static_assert(is_container::value, #c " is not a container"); read_input(c, __VA_ARGS__) #define rcont(...) __VA_ARGS__ RCONT_IMPL #define rvec(...) rcont(std::vector<__VA_ARGS__>) struct is_readable_impl { template auto operator() (T t) -> decltype(std::cin >> t); }; template struct is_readable : is_valid {}; template std::enable_if_t{}> read_input(T&, std::size_t); template void read_input(std::pair&); template std::enable_if_t{}> read_input(T&); template std::enable_if_t{}> read_input(T&, std::size_t , std::size_t, std::size_t); template std::enable_if_t{}> read_input(T& value) { std::cin >> value; } template std::enable_if_t{}> read_input(T& value, T offset) { read_input(value); value -= offset; } template std::enable_if_t{}> read_input(T& container, std::size_t n) { container = T(n); read_input(container); } template void read_input(std::pair& pair) { read_input(pair.first); read_input(pair.second); } template std::enable_if_t{}> read_input(T& container) { for (auto& elem : container) read_input(elem); } template std::enable_if_t{}> read_input(T& container, std::size_t n, std::size_t sentinel_l, std::size_t sentinel_r) { container = T(n); for (auto& elem : slice(container, sentinel_l, sentinel_r)) { read_input(elem); } } template std::ostream& operator<<(std::ostream& os, std::pair pair) { os << '(' << pair.first << ", " << pair.second << ')'; return os; } template std::enable_if_t{}, std::ostream&> operator<< (std::ostream& os, C container) { os << '[' << *std::begin(container); for (auto& elem : slice(container, 1)) { os << ' ' << elem; } os << ']'; return os; } void accelerate_IO() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } // }}} // Debugging {{{ #ifdef DEBUG # define show(expr) std::cerr << "\e[33m[Show : line " << __LINE__ << "] " << #expr << " = " << (expr) << "\e[m" << std::endl # define msg(message) std::cerr << "\e[33m[Message : line " << __LINE__ << "] " << message << "\e[m" << std::endl # define debug if (true) #else # define show(expr) inline void msg(...) {} # define debug if (false) #endif // }}} using namespace std; int main() { rz(n); rvec(pair)(es, n - 1); vector> gr(n); vector exist(n, true); each(p, es) { p.first--; p.second--; gr[p.first].insert(p.second); gr[p.second].insert(p.first); } bool leaf = true; while (leaf) { leaf = false; rep(i, n) { show(i); if (!exist[i] || gr[i].size() != 1) continue; show(gr[i]); leaf = true; auto deleted = *begin(gr[i]); show(deleted); each(u, gr[deleted]) { show(u); gr[u].erase(deleted); } gr[deleted].clear(); exist[deleted] = false; } } Z parts = 0; rep(i, n) if (exist[i]) parts++; cout << parts << endl; }