#include template class TreeDP { public: TreeDP(const std::vector>& edges, std::function op2, std::function op1, T identity = T()) : edges_(edges), op2_(op2), op1_(op1), identity_(identity) { dp_.resize(edges.size()); for (std::size_t i = 0; i < edges.size(); ++i) { dp_[i].resize(edges[i].size()); } result_.resize(edges.size()); } void DFS(int root) { // Use a stack to avoid potential stack overflows. std::stack> s; s.push({root, -1, -1, true}); while (!s.empty()) { auto [node, parent, parent_index, enter] = s.top(); s.pop(); if (enter) { s.push({node, parent, parent_index, false}); for (std::size_t i = 0; i < edges_[node].size(); ++i) { if (int child = edges_[node][i]; child != parent) { s.push({child, node, i, true}); } } } else { T t = identity_; for (std::size_t i = 0; i < edges_[node].size(); ++i) { if (int child = edges_[node][i]; child != parent) { t = op2_(t, dp_[node][i]); } } if (parent != -1) { dp_[parent][parent_index] = op1_(t); } } } } void Rerooting(int root) { std::stack> s; s.push({root, -1, identity_}); while (!s.empty()) { auto [node, parent, parent_result] = s.top(); s.pop(); const std::vector edges = edges_[node]; std::vector& dp = dp_[node]; if (parent != -1) { for (std::size_t i = 0; i < edges.size(); ++i) { if (edges[i] == parent) { dp[i] = parent_result; } } } // lower[i] = op2_(dp[i - 1], op2_(dp[i - 2], ...)) std::vector lower(edges.size() + 1); lower[0] = identity_; for (std::size_t i = 0; i < edges.size(); ++i) { lower[i + 1] = op2_(lower[i], dp[i]); } // higher[i] = op2_(dp[i], op2_(dp[i + 1], ...)) std::vector higher(edges.size() + 1); higher[edges.size()] = identity_; for (std::size_t i = edges.size() - 1; i < edges.size(); --i) { higher[i] = op2_(higher[i + 1], dp[i]); } result_[node] = op1_(higher[0]); for (std::size_t i = 0; i < edges.size(); ++i) { if (int child = edges[i]; child != parent) { s.push({child, node, op1_(op2_(lower[i], higher[i + 1]))}); } } } } const std::vector>& DP() const { return dp_; } const std::vector& Result() const { return result_; } private: std::vector> edges_; const std::function op2_; const std::function op1_; const T identity_; std::vector> dp_; std::vector result_; }; #include template struct is_iterable : std::false_type {}; template struct is_iterable())), decltype(std::end(std::declval()))>> : std::true_type {}; template struct is_pair : std::false_type {}; template struct is_pair().first), decltype(std::declval().second)>> : std::true_type {}; template void debug(const T& v) { if constexpr (is_pair::value) { std::cerr << "{"; debug(v.first); std::cerr << ", "; debug(v.second); std::cerr << "}"; } else if constexpr (is_iterable::value && !std::is_same::value) { std::cerr << "{"; for (auto it = std::begin(v); it != std::end(v); ++it) { if (it != std::begin(v)) std::cerr << ", "; debug(*it); } std::cerr << "}"; } else { std::cerr << v; } } template void debug(const T& value, const Ts&... args) { debug(value); std::cerr << ", "; debug(args...); } #if DEBUG #define dbg(...) \ do { \ cerr << #__VA_ARGS__ << ": "; \ debug(__VA_ARGS__); \ cerr << " (L" << __LINE__ << ")\n"; \ } while (0) #else #define dbg(...) #endif void read_from_cin() {} template void read_from_cin(T& value, Ts&... args) { std::cin >> value; read_from_cin(args...); } #define rd(type, ...) \ type __VA_ARGS__; \ read_from_cin(__VA_ARGS__); #define ints(...) rd(int, __VA_ARGS__); #define strings(...) rd(string, __VA_ARGS__); template void write_to_cout(const T& value) { if constexpr (std::is_same::value) { std::cout << (value ? "Yes" : "No"); } else { std::cout << value; } } template void write_to_cout(const T& value, const Ts&... args) { write_to_cout(value); std::cout << ' '; write_to_cout(args...); } #define wt(...) \ do { \ write_to_cout(__VA_ARGS__); \ cout << '\n'; \ } while (0) #define all(x) (x).begin(), (x).end() #define rep_dispatch(_1, _2, _3, name, ...) name #define rep3(i, a, b) for (int i = (int)(a); i < (int)(b); ++i) #define rep2(i, n) rep3(i, 0, n) #define rep1(n) rep2(_loop_variable_, n) #define rep(...) rep_dispatch(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define rrep3(i, a, b) for (int i = (int)(b)-1; i >= a; --i) #define rrep2(i, n) rrep3(i, 0, n) #define rrep1(n) rrep2(_loop_variable_, n) #define rrep(...) rep_dispatch(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__) template std::istream& operator>>(std::istream& is, std::vector& v) { for (T& vi : v) is >> vi; return is; } template std::istream& operator>>(std::istream& is, std::pair& p) { is >> p.first >> p.second; return is; } template bool chmax(T& a, U b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, U b) { if (a > b) { a = b; return true; } return false; } template T max(T a, U b) { return a > b ? a : b; } template T mix(T a, U b) { return a < b ? a : b; } template int sz(const T& v) { return v.size(); } template int popcount(T i) { return std::bitset::digits>(i).count(); } using i64 = std::int64_t; using i32 = std::int32_t; template using low_priority_queue = std::priority_queue, std::greater>; template using V = std::vector; template using VV = V>; void Main(); int main() { Main(); return 0; } const auto& Fix = boost::hana::fix; using namespace std; #define int i64 void Main() { ints(n); VV edges(n); rep(n - 1) { ints(a, b); --a, --b; edges[a].push_back(b); edges[b].push_back(a); } TreeDP tdp( edges, [](bool a, bool b) { return a || b; }, [](bool a) { return !a; }, false); tdp.DFS(0); tdp.Rerooting(0); V ans; rep(i, n) if (tdp.Result()[i]) ans.push_back(i); wt(sz(ans)); for (int i : ans) wt(i + 1); }