結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
|
提出日時 | 2021-11-06 14:08:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 4,305 bytes |
コンパイル時間 | 3,804 ms |
コンパイル使用メモリ | 227,196 KB |
最終ジャッジ日時 | 2025-01-25 14:08:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
// clang-format off#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>#define mp make_pair#define fst first#define snd second#define forn(i,n) for (int i = 0; i < int(n); i++)#define forn1(i,n) for (int i = 1; i <= int(n); i++)#define popcnt __builtin_popcountll#define ffs __builtin_ffsll#define ctz __builtin_ctzll#define clz __builtin_clz#define clzll __builtin_clzll#define all(a) (a).begin(), (a).end()using namespace std;using namespace __gnu_pbds;using uint = unsigned int;using ll = long long;using ull = unsigned long long;using pii = pair<int,int>;using pli = pair<ll,int>;using pil = pair<int,ll>;using pll = pair<ll,ll>;template <typename T> using vec = vector<T>;using vi = vec<int>;using vl = vec<ll>;template <typename T> using que = queue<T>;template <typename T> using deq = deque<T>;template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;template <typename K, typename V> using ordered_map = tree<K, V, less<K>, rb_tree_tag, tree_order_statistics_node_update>;template <typename T> T id(T b) {return b;};template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }template <typename T> bool getf(T flag, size_t i) { return (flag>>i) & 1; }template <typename T> T setf(T flag, size_t i) { return flag | (T(1)<<i); }template <typename T> T unsetf(T flag, size_t i) { return flag & ~(T(1)<<i); }void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }// clang-format onnamespace aclext {template <typename S, typename M, typename R, typename C,M (*merge)(M, M, int),M (*introduce)(M, S, C, int, int),M (*em)(),R (*result)(M, int),S (*subtree)(M, int)>class Rerooting {int n;vector<vector<pair<int, C>>> g;vector<R> ans;vector<vector<S>> dp;S dfs1(int u, int p) {M s = em();int k = g[u].size();dp[u] = vector<S>(k);for (int i = 0; i < k; i++) {auto [v, c] = g[u][i];if (v == p) continue;dp[u][i] = dfs1(v, u);s = introduce(s, dp[u][i], c, u, v);}return subtree(s, u);}void dfs2(int u, S par, int p) {int k = g[u].size();for (int i = 0; i < k; i++) {auto [v, c] = g[u][i];if (v == p) {dp[u][i] = par;}}vector<M> dp_l(k + 1, em()), dp_r(k + 1, em());for (int i = 0; i < k; i++) {dp_l[i + 1] = introduce(dp_l[i], dp[u][i], g[u][i].second, u, g[u][i].first);}ans[u] = result(dp_l[k], u);for (int i = k - 1; i >= 0; i--) {dp_r[i] = introduce(dp_r[i + 1], dp[u][i], g[u][i].second, u, g[u][i].first);}for (int i = 0; i < k; i++) {auto [v, c] = g[u][i];if (v == p) continue;dfs2(v, subtree(merge(dp_l[i], dp_r[i + 1], u), u), u);}}public:Rerooting(int n): n(n), g(n), ans(n) { }void add_edge(int u, int v, C c = {}) {assert(0 <= u && u < n);assert(0 <= v && v < n);g[u].emplace_back(v, c);g[v].emplace_back(u, c);}vector<R> calc() {dp = vector<vector<S>>(n);dfs1(0, -1);dfs2(0, {}, -1);return ans;}};}using S = bool;using M = bool;using C = bool;using R = S;M merge(M a, M b, int) { return a and b; }M introduce(M a, S b, C c, int, int) { return a and !b; }M em() { return true; }R result(M a, int) { return a; }using rerooting = aclext::Rerooting<S, M, R, C, merge, introduce, em, result, result>;int main() {fastio();int n;cin >> n;rerooting r(n);forn(i, n - 1) {int u, v;cin >> u >> v;u--, v--;r.add_edge(u, v);}auto ans = r.calc();cout << count(all(ans), true) << "\n";forn(i, n) {if (ans[i]) {cout << (i + 1) << "\n";}}return 0;}