結果

問題 No.768 Tapris and Noel play the game on Treeone
コンテスト
ユーザー kkishi
提出日時 2020-09-29 08:02:17
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 7,358 bytes
コンパイル時間 5,131 ms
コンパイル使用メモリ 172,288 KB
実行使用メモリ 24,568 KB
最終ジャッジ日時 2024-07-03 12:26:50
合計ジャッジ時間 9,298 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

template <typename T>
class TreeDP {
 public:
  TreeDP(const std::vector<std::vector<int>>& edges, std::function<T(T, T)> op2,
         std::function<T(T)> 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<std::tuple<int, int, int, bool>> 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<std::tuple<int, int, T>> s;
    s.push({root, -1, identity_});

    while (!s.empty()) {
      auto [node, parent, parent_result] = s.top();
      s.pop();

      const std::vector<int> edges = edges_[node];
      std::vector<T>& 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<T> 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<T> 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<std::vector<T>>& DP() const { return dp_; }
  const std::vector<T>& Result() const { return result_; }

 private:
  std::vector<std::vector<int>> edges_;

  const std::function<T(T, T)> op2_;
  const std::function<T(T)> op1_;
  const T identity_;

  std::vector<std::vector<T>> dp_;
  std::vector<T> result_;
};
#include <boost/hana/functional/fix.hpp>

template <typename T, typename = void>
struct is_iterable : std::false_type {};
template <typename T>
struct is_iterable<T, std::void_t<decltype(std::begin(std::declval<T>())),
                                  decltype(std::end(std::declval<T>()))>>
    : std::true_type {};

template <typename T, typename = void>
struct is_pair : std::false_type {};
template <typename T>
struct is_pair<T, std::void_t<decltype(std::declval<T>().first),
                              decltype(std::declval<T>().second)>>
    : std::true_type {};

template <typename T>
void debug(const T& v) {
  if constexpr (is_pair<T>::value) {
    std::cerr << "{";
    debug(v.first);
    std::cerr << ", ";
    debug(v.second);
    std::cerr << "}";
  } else if constexpr (is_iterable<T>::value &&
                       !std::is_same<T, std::string>::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 <typename T, typename... Ts>
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 <typename T, typename... Ts>
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 <typename T>
void write_to_cout(const T& value) {
  if constexpr (std::is_same<T, bool>::value) {
    std::cout << (value ? "Yes" : "No");
  } else {
    std::cout << value;
  }
}
template <typename T, typename... Ts>
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 <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for (T& vi : v) is >> vi;
  return is;
}

template <typename T, typename U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T, typename U>
bool chmax(T& a, U b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T, typename U>
bool chmin(T& a, U b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <typename T, typename U>
T max(T a, U b) {
  return a > b ? a : b;
}

template <typename T, typename U>
T mix(T a, U b) {
  return a < b ? a : b;
}

template <typename T>
int sz(const T& v) {
  return v.size();
}

template <typename T>
int popcount(T i) {
  return std::bitset<std::numeric_limits<T>::digits>(i).count();
}

using i64 = std::int64_t;
using i32 = std::int32_t;

template <typename T>
using low_priority_queue =
    std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <typename T>
using V = std::vector<T>;
template <typename T>
using VV = V<V<T>>;

void Main();

int main() {
  Main();
  return 0;
}

const auto& Fix = boost::hana::fix;

using namespace std;

#define int i64

void Main() {
  ints(n);
  VV<i32> edges(n);
  rep(n - 1) {
    ints(a, b);
    --a, --b;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }
  TreeDP<bool> tdp(
      edges, [](bool a, bool b) { return a || b; }, [](bool a) { return !a; },
      false);
  tdp.DFS(0);
  tdp.Rerooting(0);

  V<int> ans;
  rep(i, n) if (tdp.Result()[i]) ans.push_back(i);

  wt(sz(ans));
  for (int i : ans) wt(i + 1);
}
0