結果
| 問題 | No.768 Tapris and Noel play the game on Treeone |
| ユーザー |
 baitop
|
| 提出日時 | 2021-12-18 18:15:52 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 135 ms / 2,000 ms |
| コード長 | 58,618 bytes |
| コンパイル時間 | 3,749 ms |
| コンパイル使用メモリ | 215,980 KB |
| 実行使用メモリ | 41,472 KB |
| 最終ジャッジ日時 | 2023-10-13 17:59:41 |
| 合計ジャッジ時間 | 5,800 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
4,372 KB |
| testcase_01 | AC | 1 ms
4,348 KB |
| testcase_02 | AC | 2 ms
4,348 KB |
| testcase_03 | AC | 2 ms
4,352 KB |
| testcase_04 | AC | 2 ms
4,348 KB |
| testcase_05 | AC | 2 ms
4,348 KB |
| testcase_06 | AC | 2 ms
4,352 KB |
| testcase_07 | AC | 66 ms
26,228 KB |
| testcase_08 | AC | 34 ms
15,348 KB |
| testcase_09 | AC | 39 ms
17,392 KB |
| testcase_10 | AC | 28 ms
14,192 KB |
| testcase_11 | AC | 116 ms
39,544 KB |
| testcase_12 | AC | 112 ms
40,240 KB |
| testcase_13 | AC | 112 ms
38,952 KB |
| testcase_14 | AC | 120 ms
38,304 KB |
| testcase_15 | AC | 123 ms
40,744 KB |
| testcase_16 | AC | 135 ms
40,876 KB |
| testcase_17 | AC | 122 ms
41,472 KB |
| testcase_18 | AC | 99 ms
40,420 KB |
| testcase_19 | AC | 92 ms
39,924 KB |
| testcase_20 | AC | 93 ms
39,104 KB |
| testcase_21 | AC | 90 ms
36,652 KB |
| 20evil_special_uni1.txt | AC | 113 ms
41,128 KB |
| 20evil_special_uni2.txt | AC | 105 ms
38,952 KB |
ソースコード
#include <cassert>
#include <cctype>
// #include <cerrno>
#include <cfloat>
// #include <ciso646>
#include <climits>
// #include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
// #include <cstdbool>
#include <cstdint>
// #include <ctgmath>
// #include <cuchar>
// #include <cwchar>
// #include <cwctype>
#endif //__cplusplus >= 201103L
// C++ headers
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
// #include <atomic>
#include <chrono>
// #include <codecvt>
// #include <condition_variable>
#include <forward_list>
// #include <future>
#include <initializer_list>
// #include <mutex>
#include <random>
#include <ratio>
#include <regex>
// #include <scoped_allocator>
#include <system_error>
// #include <thread>
#include <tuple>
// #include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif //__cplusplus >= 201103L
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif //__cplusplus >= 201402L
using namespace std;
struct initon {
initon() {
cin.tie(0);
ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(16);
srand((unsigned) clock() + (unsigned) time(NULL));
};
} initonv;
//@メタ meta
//template<class T, require_t(is_same<T, U>::value)>等
#define require_t(bo) enable_if_t<bo>* = nullptr
template<typename T, typename U = typename T::value_type> std::true_type value_type_tester(signed);
template<typename T> std::false_type value_type_tester(long);
template<typename T> struct has_value_type : decltype(value_type_tester<T>(0)) {};
template<class T> inline constexpr bool has_value_type_v = has_value_type<T>::value;
template<class T> struct is_vector : std::false_type {};
template<class T> struct is_vector<std::vector<T>> : std::true_type {};
template<class T> inline constexpr bool is_vector_v = is_vector<T>::value;
template<class T1, class T2, bool t1_bigger = (sizeof(T1) > sizeof(T2))> struct max_type { typedef T1 type; };
template<class T1, class T2> struct max_type<T1, T2, false> { typedef T2 type; };
//A<T>でTを返す
template<class T> using value_type_t = typename T::value_type;
//A<B<.....T>>でTを返す
template<class T, bool end = !has_value_type<T>::value> struct value_type_rec { typedef T type; };
template<class T> struct value_type_rec<T, false> { typedef typename value_type_rec<value_type_t<T>>::type type; };
template<class T> using value_type_rec_t = typename value_type_rec<T>::type;
//int == remove_extent_rec_t<int[][][]>
template<class T, bool end = is_same<T, remove_extent_t<T>>::value> struct remove_extent_rec { typedef T type; };
template<class T> struct remove_extent_rec<T, false> { typedef typename remove_extent_rec<remove_extent_t<T>>::type type; };
template<class T> using remove_extent_rec_t = typename remove_extent_rec<T>::type;
//^@メタ meta
//別名置換
#define int long long
#define ll long long
using vb = vector<bool>;
using vc = vector<char>;
using vi = vector<int>;
using vs = vector<string>;
#define sz(a) ((ll)(a).size())
#define k4 10101
#define k5 101010
#define k6 1010101
#define k7 10101010
const double PI = 3.1415926535897932384626433832795029L;
const double eps = 1e-9;
using str = string;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using F = tuple<ll, ll, ll, ll>;
#define uset unordered_set
#define mset multiset
#define umap unordered_map
//#define V vector
#define vvt0(t) vector<vector<t>>
#define vvt1(t, a) vector<vector<t>>a
#define vvt2(t, a, b) vector<vector<t>>a(b)
#define vvt3(t, a, b, c) vector<vector<t>> a(b,vector<t>(c))
#define vvt4(t, a, b, c, d) vector<vector<t>> a(b,vector<t>(c,d))
#define vv(type, ...) over4(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(type,__VA_ARGS__)
#define vvi(...) vv(ll,__VA_ARGS__)
#define vvb(...) vv(bool,__VA_ARGS__)
#define vvs(...) vv(string,__VA_ARGS__)
#define vvd(...) vv(double,__VA_ARGS__)
#define vvc(...) vv(char,__VA_ARGS__)
#define vvp(...) vv(P,__VA_ARGS__)
#define vvt(...) vv(T,__VA_ARGS__)
//記述をシンプルにする
#define over2(o1, o2, name, ...) name
#define over3(o1, o2, o3, name, ...) name
#define over4(o1, o2, o3, o4, name, ...) name
#define over5(o1, o2, o3, o4, o5, name, ...) name
#define over6(o1, o2, o3, o4, o5, o6, name, ...) name
//@ループ
#define over4(o1, o2, o3, o4, name, ...) name
#define rep1(n) for(ll rep1i = 0,rep1lim=n; rep1i < rep1lim ; ++rep1i)
#define rep2(i, n) for(ll i = 0,i##rep2lim=n; i < i##rep2lim ; ++i)
#define rep3(i, m, n) for(ll i = m,i##rep3lim=n; i < i##rep3lim ; ++i)
#define rep4(i, m, n, ad) for(ll i = m,i##rep4lim=n; i < i##rep4lim ; i+= ad)
#define rep(...) over4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
//逆順 閉区間
#define rer2(i, n) for(ll i = n; i >= 0 ; i--)
#define rer3(i, m, n) for(ll i = m,i##rer3lim=n; i >= i##rer3lim ; i--)
#define rer4(i, m, n, dec) for(ll i = m,i##rer4lim=n; i >= i##rer4lim ; i-=dec)
#define rer(...) over4(__VA_ARGS__,rer4,rer3,rer2,)(__VA_ARGS__)
constexpr ll inf = (ll) 1e9 + 100;
constexpr ll linf = (ll) 1e18 + 100;
constexpr double dinf = (double) linf * linf;
template<typename T> class fixed_point
: T {
public:
explicit constexpr fixed_point(T &&t) noexcept: T(std::forward<T>(t)) {}
template<typename... Args> constexpr decltype(auto) operator()(Args &&... args) const { return T::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T> static inline constexpr decltype(auto) fix(T &&t) noexcept { return fixed_point<T>{std::forward<T>(t)}; }
//初期値l=-1, r=-1
void set_lr12(int &a, int &b, int n) { /*b==-1*/ if (b == -1) {
if (a == -1) {
a = 0;
b = n;
} else {
b = a;
a = 0;
}
}
}
template<class T, class U> bool chma(T &a, const U &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template<class T, class U> bool chmi(T &a, const U &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T> T MAX() { return numeric_limits<T>::max(); }
template<class T> T MIN() { return numeric_limits<T>::min(); }
template<typename W, typename T> void fill(vector<W> &a, const T &v, int l = -1, ll r = -1) {
set_lr12(l, r, a.size());
if constexpr(!is_vector<W>::value) { rep(i, l, r)a[i] = v; } else { rep(i, l, r)fill(a[i], v); }
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> sum(const Iterable &a, int l = -1, int r = -1) {
value_type_rec_t<Iterable> ret = 0; /*vectorの処理*/ if constexpr(is_vector_v<Iterable>) { set_lr12(l, r, sz(a)); /*1次元なら全部足す*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>) { rep(i, l, r) ret += a[i]; } else { rep(i, l, r) ret += sum(a[i]); }} else { /*set等の処理*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>) { for (auto &v : a) { ret += v; }} else { for (auto &v : a) { ret += sum(v); }}}
return ret;
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> min(const Iterable &a, int l = -1, int r = -1) {
value_type_rec_t<Iterable> ret = MAX<value_type_rec_t<Iterable>>(); /*vectorの処理*/ if constexpr(is_vector_v<Iterable>) { set_lr12(l, r, sz(a)); /*1次元なら全部足す*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>) { rep(i, l, r) ret = min(ret, a[i]); } else { rep(i, l, r) ret = min(ret, min(a[i])); }} else { /*set等の処理*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>) { for (auto &v : a) { ret = min(ret, v); }} else { for (auto &v : a) { ret = min(ret, min(v)); }}}
return ret;
}
template<class Iterable, require_t(has_value_type_v<Iterable>)> value_type_rec_t<Iterable> max(const Iterable &a, int l = -1, int r = -1) {value_type_rec_t<Iterable> ret = MIN<value_type_rec_t<Iterable>>(); /*vectorの処理*/ if constexpr(is_vector_v<Iterable>) { set_lr12(l, r, sz(a)); /*1次元なら全部足す*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>){ rep(i, l, r) ret = max(ret, a[i]); }else{ rep(i, l, r) ret = max(ret, max(a[i])); } } else { /*set等の処理*/ if constexpr(!has_value_type_v<value_type_t<Iterable>>){ for (auto &v : a) { ret = max(ret, v); } }else{ for (auto &v : a) { ret = max(ret, max(v)); } } } return ret;}/*@formatter:off*/
template<class Array, class T, size_t N> void fill(Array(&a)[N] , const T& v, int l = -1, int r = -1) { set_lr12(l, r, N); if constexpr(is_same_v<Array, remove_extent_t<Array>>){ rep(i, l, r) a[i] = v; }else{ rep(i, l, r) fill(a[i], v); }}
template<class Array, size_t N> remove_extent_rec_t<Array> sum(const Array(&a)[N] , int l = -1, int r = -1) { remove_extent_rec_t<Array> ret = 0; set_lr12(l, r, N); if constexpr(is_same_v<Array, remove_extent_t<Array>>){ rep(i, l, r) ret += a[i]; }else{ rep(i, l, r) ret += sum(a[i]); } return ret;}
template<class Array, size_t N> remove_extent_rec_t<Array> min(const Array(&a)[N] , int l = -1, int r = -1) { remove_extent_rec_t<Array> ret = MAX<remove_extent_rec_t<Array>>(); set_lr12(l, r, N); if constexpr(is_same_v<Array, remove_extent_t<Array>>){ rep(i, l, r) ret = std::min(ret, a[i]); }else{ rep(i, l, r) ret = std::min(ret, min(a[i])); } return ret;}
template<class Array, size_t N> remove_extent_rec_t<Array> max(const Array(&a)[N] , int l = -1, int r = -1) { remove_extent_rec_t<Array> ret = MIN<remove_extent_rec_t<Array>>(); set_lr12(l, r, N); if constexpr(is_same_v<Array, remove_extent_t<Array>>){ rep(i, l, r) ret = std::max(ret, a[i]); }else{ rep(i, l, r) ret = std::max(ret, max(a[i])); } return ret;}
template<class T> void na(vector<T> &A, int N) {A.resize(N);for (int i = 0; i < N; i++) { cin >> A[i]; }}
#define fora(a, A) for(auto& a : A)
#define ALL(A) (A).begin(), (A).end()
template<class T, class U> pair<T, U> operator+=(pair<T,U> &a, const pair<T,U> & b) {a.fi+=b.fi;a.se+=b.se; return a;}
template<class T, class U> pair<T, U> operator+(const pair<T, U> &a, const pair<T, U> &b) { pair<T, U> c = a;c += b;return c;}
template<class T, class U> pair<T, U> operator-=(pair<T,U> &a, const pair<T,U> & b) {a.fi-=b.fi;a.se-=b.se; return a;}
template<class T, class U> pair<T, U> operator-(const pair<T, U> &a, const pair<T, U> &b) { pair<T, U> c = a;c -= b;return c;}
template<class T, class U, class V> pair<T, U> operator*=(pair<T, U> &a, const V& b) { a.fi*=b;a.se*=b; return a;}
template<class T, class U, class V> pair<T, U> operator*(const pair<T, U> &a, const V& b) { pair<T, U> c = a;c *= b;return c; }
template<class T, class U, class V> pair<T, U> operator/=(pair<T, U> &a, const V& b) { a.fi/=b;a.se/=b; return a;}
template<class T, class U, class V> pair<T, U> operator/(const pair<T, U> &a, const V& b) { pair<T, U> c = a;c /= b;return c; }
template<class T, class U> pair<T, U> operator-(const pair<T, U> &a) { return pair<T, U>(-a.first, -a.second); }
/*@formatter:on*/
#define deb(...)
#define endl '\n'
//int inf = 1<<30;
//long long linf = 1ll<<60;
//double dinf = 1ll<<60;
//#define assert2(...)
namespace {/*@formatter:off*/
template<class T> T INF() { return numeric_limits<T>::max() / 2; }
template<> signed INF() { return inf; }
template<> ll INF() { return linf; }
template<> double INF() { return dinf; }
template<> char INF() { return '{'; }
template<> string INF() { return "{"; }
void ole() {
#ifdef _DEBUG
cerr << "ole" << endl;exit(0);
#endif
string a = "a"; rep(i, 30)a += a; rep(i, 1 << 17)cout << a << endl; cout << "OLE 出力長制限超過" << endl;exit(0);
}
void re(string s = "") {cerr << s << endl;assert(0 == 1);exit(0);}
void tle() { while (inf)cout << inf << endl; }
#undef getid
#undef getid_1
#undef getid_2
#define forg_f_init(ve) int f = ve[gi].f, t = ve[gi].t; auto& c = ve[gi].c
#define forg_f(gi, ve) for (ll gi = 0,forg_flim = ve.size(); gi < forg_flim; ++gi)
#define fort_f(gi, ve) for (ll gi = 0,forg_flim = ve.size(); gi < forg_flim ; ++gi)
#define fort_f_init(gi, ve) int f = ve[gi].f, t = ve[gi].t, c = ve[gi].c;if(t == p)continue;
#define fore(gi, ve) for (ll gi = 0,forg_flim = ve.size(), f, t, c; gi < forg_flim && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi)
template<class T> struct edge_ {
typedef T value_type;
int f, t;
T c;
edge_(int f, int t, T c = 1) : f(f), t(t), c(c) {}
bool operator<(const edge_ &b) const { return c < b.c; }
bool operator>(const edge_ &b) const { return c > b.c; }
};
template<class T> ostream &operator<<(ostream &os, edge_<T> &e) {os << e.f << " " << e.t << " " << e.c;return os;}
template<typename T> class graph {
public :
typedef T value_type;
vector<vector<edge_<T>>> g;
vector<edge_<T>> edges;
int n;
explicit graph(int n) : n(n) { g.resize(n); }
void clear() { g.clear(), edges.clear(); }
void resize(int n) {this->n = n;g.resize(n);}
int size() { return n; }
vector<edge_<T> > &operator[](int i) { return g[i]; }
virtual void add(int f, int t, T c) = 0;
virtual void set_edges() = 0;
};
template<typename T =ll> class digraph : public graph<T> {
public:
using graph<T>::g;
using graph<T>::n;
using graph<T>::edges;
explicit digraph(int n) : graph<T>(n) {}
explicit digraph(int n, const vector<edge_<T>>& E) : graph<T>(n) { fora(e,E){ add(e.f,e.t,e.c); } }
void add(int f, int t, T c = 1) {
if (!(0 <= f && f < n && 0 <= t && t < n)) {cerr<<"digraph add"<<endl;deb(f, t, c);ole();}
g[f].emplace_back(f, t, c);
edges.emplace_back(f, t, c);//edgesを使わないなら消せる
}
void ing(int n, int m, int minus = 1) { this->resize(n); rep(i, m) { int f, t; cin >> f >> t; f -= minus; t -= minus; add(f, t); } }
void ingc(int n, int m, int minus = 1) { this->resize(n); rep(i, m) { int f, t, c; cin >> f >> t >> c; f -= minus; t -= minus; add(f, t, c); } }
void set_edges() override{ if (sz(edges))return; rep(i, n)fora(e, g[i])edges.push_back(e); }
};
#define unionfind unionfind_graph
struct unionfind {
vector<ll> par;
vector<ll> siz;
vector<ll> es;
ll n, trees;//連結グループの数(親の種類)
unionfind(ll n) : n(n), trees(n) { par.resize(n); siz.resize(n); es.resize(n); for (ll i = 0; i < n; i++) { par[i] = i; siz[i] = 1; } }
template<class T>unionfind(graph<T>& g) : n(g.n), trees(g.n) { par.resize(n); siz.resize(n); es.resize(n); for (ll i = 0; i < n; i++) { par[i] = i; siz[i] = 1; } add(g); }
ll root(ll x) { if (par[x] == x) { return x; } else { return par[x] = root(par[x]); }}
ll operator()(ll x){return root(x);}
bool unite(ll x, ll y) { x = root(x); y = root(y); es[x]++; if (x == y) return false; if (siz[x] > siz[y]) swap(x, y); trees--; par[x] = y; siz[y] += siz[x]; es[y] += es[x]; return true; }
template<class T>void add(graph<T>&g){fora(e,g.edges){unite(e.f,e.t);}}
template<class T>void unite(graph<T>&g){add(g);}
bool same(ll x, ll y) { return root(x) == root(y); }
ll size(ll x) { return siz[root(x)]; }
ll esize(ll x) { return es[root(x)]; }
vi sizes(){ vi cou(n); vi ret; ret.reserve(n); rep(i, n){ cou[root (i)]++; } rep(i, n){ if(cou[i])ret.push_back(cou[i]); } return ret; }
//つながりを無向グラフと見なし、xが閉路に含まれるか判定
bool close(ll x) { return esize(x) >= size(x); }
vector<vi> sets() { vi ind(n, -1); ll i = 0; vvi(res, trees); rep(j, n) { ll r = root(j); if (ind[r] == -1)ind[r] = i++; res[ind[r]].push_back(j); } rep(i, trees) { ll r = root(res[i][0]); if (res[i][0] == r)continue; rep(j, 1, sz(res[i])) { if (res[i][j] == r) { swap(res[i][0], res[i][j]); break; } } } return res; }
};//@formatter:off
#define UNDIG_WITH_UNIONFIND
template<class T=int> class undigraph : public graph<T> {
public:
using graph<T>::g; using graph<T>::n; using graph<T>::edges;
#ifdef UNDIG_WITH_UNIONFIND
//頂点の連結
//属するサイズ
//連結している辺の数などが分かる
unionfind uf;
explicit undigraph(int n) : graph<T>(n), uf(n) {}
explicit undigraph(int n, const vector<edge_<T>>& E) : graph<T>(n), uf(n) { fora(e,E){ add(e.f,e.t,e.c); uf.unite(e.f, e.t); } }
#else
explicit undigraph(int n) : graph<T>(n) {}
explicit undigraph(int n, const vector<edge_<T>>& E) : graph<T>(n) { fora(e,E){ add(e.f,e.t,e.c); } }
#endif
// f < t
void add(int f, int t, T c = 1) {
if (!(0 <= f && f < n && 0 <= t && t < n)) { cerr<<("undigraph add")<<endl; deb(f, t, c); ole(); }
g[f].emplace_back(f, t, c);
g[t].emplace_back(t, f, c);
edges.emplace_back(f, t, c);//edgesを使わないなら消せる
edges.emplace_back(t, f, c);
#ifdef UNDIG_WITH_UNIONFIND
uf.unite(f, t);
#endif
}
void add(edge_<T> &e) { int f = e.f, t = e.t; T c = e.c; add(f, t, c); }
void ing(int n, int m, int minus = 1) { this->resize(n); rep(i, m) { int f, t; cin >> f >> t; f -= minus; t -= minus; add(f, t); } }
void ingc(int n, int m, int minus = 1) { this->resize(n); rep(i, m) { int f, t, c; cin >> f >> t >> c; f -= minus; t -= minus; add(f, t, c); } }
void set_edges () override{ if (sz(edges))return; rep(i, n)fora(e, g[i])edges.push_back(e); }
//iを含む、連結成分を返す
vector<int> sames(int i){ vector<int> nodes; unordered_set<int> was; queue<int> q; q.push(i); was.insert(i); nodes.push_back(i); while(!q.empty()){ int i = q.front(); q.pop(); for(auto& e : g[i]){ if(was.find(e.t) != was.end())continue; was.insert(e.t); nodes.push_back(e.t); q.push(e.t); } } return nodes; }
#ifdef UNDIG_WITH_UNIONFIND
using graph<T>::size;
int root_uf(int i){return uf.root(i);}
//iの連結連結成分のサイズを返す
int size(int i){return uf.size(i);}
int esize(int i){return uf.esize(i);}
bool same(int i, int j){return uf.same(i, j);}
//iの連結成分がなもりグラフ(n頂点n辺)かを返す
bool is_namori(int i){return uf.size(i) == uf.esize(i);}
bool is_namori() {return uf.size(0) == n && uf.esize(0) == n;}
#endif
};
#define dijkstra_path dis_path
template<class T,class I> vi dis_path(digraph<T> &g, vector<T> &dis, int s, int t, I init_value) { assert(dis[t] != init_value); auto rg = rev(g); int now = t; vi path; path.push_back(now); T cost = 0; while (now != s) { rep(gi, sz(rg[now])) { int m = rg[now][gi].t; if (dis[m] == init_value)continue; if (dis[m] + rg[now][gi].c + cost == dis[t]) { cost += rg[now][gi].c; now = m; break; } } path.push_back(now); } std::reverse(path.begin(), path.end()); return path;}
template<class T,class I> vi dis_path(undigraph<T> &g, vector<T> &dis, int s, int t, I init_value) { assert(dis[t] != init_value); int now = t; vi path; path.push_back(now); T cost = 0; while (now != s) { rep(gi, sz(g[now])) { int m = g[now][gi].t; if (dis[m] == init_value)continue; if (dis[m] + g[now][gi].c + cost == dis[t]) { cost += g[now][gi].c; now = m; break; } } path.push_back(now); } reverse(path.begin(), path.end()); return path;}
template<class T,class I> vi dis_path(digraph<T> &g, vector<vector<T>> &dis, int s, int t, I init_value) { return dis_path(g, dis[s], s, t, init_value); }
template<class T,class I> vi dis_path(undigraph<T> &g, vector<vector<T>> &dis, int s, int t, I init_value) { return dis_path(g, dis[s], s, t, init_value); }
vi to_vi(const int& i){return vi{i};}
vi to_vi(const vi& v){return v;}
#define dijk dijkstra
//O(N^2)
template<class T, class U, class I> vector<T> dijkstra_mitu(graph<T> &g, const U &S_, I init_value) { vi S = to_vi(S_); int n = g.n; T initValue = numeric_limits<T>::max(); vector<T> dis(n, initValue); fora(s, S) { if (!(0 <= s && s < g.n)) { cerr<<("dijkstra_mitu")<<endl; deb(s, g.n); ole(); } dis[s] = 0; } vb used(n); while (true) { int v = -1; rep(u, n) { if (!used[u] && (v == -1 || dis[u] < dis[v]))v = u; } if (v == -1)break; if (dis[v] == initValue)break; used[v] = true; rep(u, sz(g[v])) { auto e = g[v][u]; dis[e.t] = min(dis[e.t], dis[v] + e.c); } } /*基本、たどり着かないなら-1*/ for (auto &&d :dis) { if (d == initValue) { d = init_value; }} return dis;}
template<class T, class U, class I> vector<T> dijkstra_01(graph<T> &g, const U &S_, I init_value) {int N = g.n; vi S = to_vi(S_); T tinf = INF<T>(); vector<T> dis(N, tinf); deque<int> q; fora(s, S) { dis[s] = 0; q.push_back(s); } vb was(N); while (!q.empty()) { int f = q.front(); q.pop_front(); if (was[f])continue; was[f] = true; fora(e, g[f]) { if (dis[e.t] > dis[f] + e.c) { if (e.c) { dis[e.t] = dis[f] + 1; q.push_back(e.t); } else { dis[e.t] = dis[f]; q.push_front(e.t); } } } } rep(i, N)if (dis[i] == tinf)dis[i] = init_value; return dis;}
template<typename T> struct radixheap { vector<pair<unsigned long long, T> > v[65]; unsigned long long size_, last; radixheap() : size_(0), last(0) {} bool empty() const { return size_ == 0; } int getbit(int a) { return a ? 64 - __builtin_clzll(a) : 0; } void emplace(unsigned long long key, const T &value) { ++size_; v[getbit(key ^ last)].emplace_back(key, value); } void push(unsigned long long key, const T &value) { emplace(key, value); } pair<unsigned long long, T> top() { if (v[0].empty()) { int idx = 1; while (v[idx].empty()) ++idx; last = min_element(begin(v[idx]), end(v[idx]))->first; for (auto &p : v[idx]) v[getbit(p.first ^ last)].emplace_back(p); v[idx].clear(); } --size_; auto ret = v[0].back(); v[0].pop_back(); return ret; } void pop() { ; } int size() { return size_; }};
//01, 密グラフ, normalを自動で判断する
template<class Q, class T, class U,class I> vector<T> private_dijkstra(graph<T> &g, U &S_, I init_value) { vi S = to_vi(S_); fora(s, S) { if (!(0 <= s && s < g.n)) { cerr<<("dijkstra")<<endl; deb(s, g.n); ole(); } } bool cost01 = true; rep(i, g.n) { forg_f(gi, g[i]) {forg_f_init(g[i]); cost01 &= (c == 0 || c == 1); }} if (cost01)return dijkstra_01(g, S_, init_value); else if ((g.n + sz(g.edges)) * log2(g.n) > g.n * g.n) { return dijkstra_mitu(g, S, init_value); } T initValue = numeric_limits<T>::max(); vector<T> dis(g.n, initValue); Q q; fora(s, S) { dis[s] = 0; q.emplace(0, s); } while (q.size()) { T nowc; int i; tie(nowc, i) = q.top(); q.pop(); if (dis[i] != nowc)continue; for (auto &&e : g.g[i]) { int to = e.t; T c = nowc + e.c; if (dis[to] > c) { dis[to] = c; q.emplace(dis[to], to); } } } /*基本、たどり着かないなら-1*/ for (auto &&d :dis) if (d == initValue)d = init_value; return dis;}
//O((N+M)log(N))
template<class T, class U,class I> vector<T> dijkstra(graph<T> &g, U S_, I init_value) { if (typeid(T) == typeid(int)) { return private_dijkstra<radixheap<int>>(g, S_, init_value); } else { return private_dijkstra<priority_queue<pair<T, int>, vector<pair<T, int >>, greater<pair<T, int >> >>(g, S_, init_value); }}
//dijkstra_cou<mint> : 数える型で書く return vp(dis,cou)
template<class COU,class T=int,class I> auto dijkstra_cou(const graph<T> &g, int s, I init_value) { if (!(0 <= s && s < g.n)) { cerr<<("dijkstra")<<endl; deb(s, g.n); ole(); } cerr<<("count by type COU ")<<endl; cerr<<"int or mint"<<endl; T initValue = numeric_limits<T>::max(); vector<T> dis(g.n, initValue); vector<COU> cou(g.n); cou[s] = 1; priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q; dis[s] = 0; q.emplace(0, s); while (q.size()) { T nowc = q.top().fi; int i = q.top().se; q.pop(); if (dis[i] != nowc)continue; for (auto &&e : g.g[i]) { int to = e.t; T c = nowc + e.c; if (dis[to] > c) { dis[to] = c; cou[to] = cou[e.f]; q.emplace(dis[to], to); } else if (dis[to] == c) { cou[to] += cou[e.f]; } } } /*基本、たどり着かないなら-1*/ for (auto &&d :dis) if (d == initValue)d = init_value; return vtop(dis, cou);}
//コストを無限に減らせる := -linf
//たどり着けない := linf
template<class T> vector<T> bell(graph<T> &g, int s) { if (g.n >= 1e4) { cout << "bell size too big" << endl; exit(0); } vector<T> res(g.n, linf); res[s] = 0; vb can(g.n); /*頂点から行けない頂点を持つ、辺を消しておく */ fix([&](auto ds, int p, int i) -> void { if (can[i])return; can[i] = true; forg_f(gi, g[i]){ forg_f_init(g[i]); if (t != p)ds(i, t); } })(-1, 0); vector<edge_<T>> es; fora(e, g.edges) { if (can[e.f])es += e; } rep(i, g.n) { bool upd = false; fora(e, es) { if (res[e.f] != linf && res[e.t] > res[e.f] + e.c) { upd = true; res[e.t] = res[e.f] + e.c; } } if (!upd)break; } rep(i, g.n * 2) { bool upd = 0; fora(e, g.edges) { if (res[e.f] != linf && res[e.t] != -linf && res[e.t] > res[e.f] + e.c) { upd = 1; res[e.t] = -linf; } } if (!upd)break; } return res; }
//コストを無限に増やせる := linf
//たどり着けない := -linf
template<class T> vector<T> bell_far(graph<T> &g, int s) { if (g.n >= 1e4) { cout << "bell_far size too big" << endl; exit(0); } vector<T> res(g.n, linf); res[s] = 0; vb can(g.n); /*頂点から行けない頂点を持つ、辺を消しておく*/ fix([&](auto ds, int p, int i) -> void { if (can[i])return; can[i] = true; forg_f(gi, g[i]){ forg_f_init(g[i]); if (t != p)ds(i, t); } })(-1, 0); vector<edge_<T>> es; fora(e, g.edges) { if (can[e.f])es += e; } rep(i, g.n) { bool upd = false; fora(e, es) { if (res[e.f] != linf && res[e.t] > res[e.f] - e.c) {/*-c*/ upd = true; res[e.t] = res[e.f] - e.c;/*-c*/ } } if (!upd)break; } rep(i, g.n * 2) { bool upd = 0; fora(e, g.edges) { if (res[e.f] != linf && res[e.t] != -linf && res[e.t] > res[e.f] - e.c) {/*-c*/ upd = 1; res[e.t] = -linf; } } if (!upd)break; } rep(i, g.n)res[i] *= -1; return res; }
//コストが負の場合も扱えたはず
template<class T, class I> vector<vector<T>> warshall(graph<T> &g, I init_value) { int n = g.n; assert(n < 1e4); vector<vector<T> > dis(n, vector<T>(n, INF<T>())); rep(i, n)fora(e, g.g[i]) { if (dis[e.f][e.t] > e.c) { dis[e.f][e.t] = e.c; }} rep(i, n)dis[i][i] = 0; rep(k, n) rep(i, n) rep(j, n) { if (dis[i][j] > dis[i][k] + dis[k][j]) { dis[i][j] = dis[i][k] + dis[k][j]; }} rep(i, n)rep(j, n) if (dis[i][j] == linf)dis[i][j] = init_value; return dis;}
//密グラフの時、warshallに投げる
//01等の判定もここで出来る
template<class T, class I> vector<vector<T>> dijkstra_all(graph<T> &g, I init_value) { int n = g.n; assert(n < 1e4); if (n * n < (n + sz(g.edges)) * 14) { /*O(N^3) vs O(N (N+M)log N)*/ return warshall(g, init_value); } vector<vector<T>> dis(n); rep(i, n) { dis[i] = dijkstra(g, i, init_value); } return dis;}
template<class T> class MinOp { public: T operator()(T a, T b) { return min(a, b); }};
template<typename OpFunc> struct SparseTable { OpFunc op; signed size; vector<signed> lg; vector<vector<pair<signed, signed>>> table; void init( vector<pair<signed, signed>> &array, OpFunc opfunc) { signed n = array.size(); op = opfunc; lg.assign(n + 1, 0); for (signed i = 1; i <= n; i++) { lg[i] = 31 - __builtin_clz(i); } table.assign(lg[n] + 1, array); for (signed i = 1; i <= lg[n]; i++) { for (signed j = 0; j < n; j++) { if (j + (1 << (i - 1)) < n) { table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]); } else { table[i][j] = table[i - 1][j]; }}} } pair<signed, signed> query(signed l, signed r) { assert(l < r); return op(table[lg[r - l]][l], table[lg[r - l]][r - (1 << lg[r - l])]); }};
struct PMORMQ { vector<signed> a; SparseTable<MinOp<pair<signed, signed> > > sparse_table; vector<vector<vector<signed> > > lookup_table; vector<signed> block_type; signed block_size, n_block; void init( vector<signed> &array) { a = array; signed n = a.size(); block_size = std::max(1, (31 - __builtin_clz(n)) / 2); while (n % block_size != 0) { a.push_back(a.back() + 1); n++; } n_block = n / block_size; vector<pair<signed, signed> > b(n_block, make_pair(INT_MAX, INT_MAX)); for (signed i = 0; i < n; i++) { b[i / block_size] = min(b[i / block_size], make_pair(a[i], i)); } sparse_table.init(b, MinOp<pair<signed, signed> >()); block_type.assign(n_block, 0); for (signed i = 0; i < n_block; i++) { signed cur = 0; for (signed j = 0; j < block_size - 1; j++) { signed ind = i * block_size + j; if (a[ind] < a[ind + 1]) { cur |= 1 << j; } } block_type[i] = cur; } lookup_table.assign(1 << (block_size - 1), vector<vector<signed> >(block_size, vector<signed>(block_size + 1))); for (signed i = 0; i < (1 << (block_size - 1)); i++) { for (signed j = 0; j < block_size; j++) { signed res = 0; signed cur = 0; signed pos = j; for (signed k = j + 1; k <= block_size; k++) { lookup_table[i][j][k] = pos; if (i & (1 << (k - 1))) { cur++; } else { cur--; } if (res > cur) { pos = k; res = cur; } } } } } signed query(signed l, signed r) { assert(l < r); signed lb = l / block_size; signed rb = r / block_size; if (lb == rb) { return lb * block_size + lookup_table[block_type[lb]][l % block_size][r % block_size]; } signed pl = lb * block_size + lookup_table[block_type[lb]][l % block_size][block_size]; signed pr = rb * block_size + lookup_table[block_type[rb]][0][r % block_size]; signed pos = pl; if (r % block_size > 0 && a[pl] > a[pr]) { pos = pr; } if (lb + 1 == rb) { return pos; } signed spv = sparse_table.query(lb + 1, rb).second; if (a[pos] > a[spv]) { return spv; } return pos; }};
template<class T=int> class tree : public undigraph<T> {
PMORMQ rmq; int cnt; vector<signed> id_, in; bool never = true; bool never_hld = true;
void dfs(int x, int p, int d, int dis = 0) { id_[cnt] = x; par_[x] = p; rmq_dep.push_back(d); disv[x] = dis; in[x] = cnt++; forg_f(gi, g[x]) { forg_f_init(g[x]); if (t == p) { continue; } dfs(t, x, d + 1, dis + c); id_[cnt] = x; rmq_dep.push_back(d); cnt++; } } void precalc() { never = false; cnt = 0; rmq_dep.clear(); disv.assign(n, 0); in.assign(n, -1); id_.assign(2 * n - 1, -1); par_.assign(n, -1); dfs(root, -1, 0); rmq.init(rmq_dep);
#ifdef _DEBUG
if (n >= 100)return; cerr << "---tree---" << endl; rep(i, n) { if (!(i == root || sz(g[i]) > 1))continue; cerr << i << " -> "; vi ts; forg_f(gi, g[i]) { forg_f_init(g[i]); if (t != par_[i])ts.push_back(t); } rep(i, sz(ts) - 1)cerr << ts[i] << ", "; if (sz(ts))cerr << ts.back() << endl; } cerr << endl;
#endif
} int pos; void hld_build() { never_hld = false; if (never)precalc(); g.resize(n); vid.resize(n, -1); head.resize(n); heavy.resize(n, -1); depth.resize(n); inv.resize(n); subl.resize(n); subr.resize(n); dfs(root, -1); t = 0; dfs_hld(root);
#ifdef _DEBUG
if (n >= 100)return; cerr << "---hld_index---" << endl; vi inds; rep(i, n) if (sz(g[i]))inds.push_back(i); rep(i, sz(inds)) { str s = tos(bel(inds[i])); cerr << std::right << std::setw(sz(s) + (i ? 1 : 0)) << inds[i]; } cerr << endl; rep(i, sz(inds)) { cerr << bel(inds[i]) << " "; } cerr << endl << endl; cerr << "---hld_edge_index---" << endl; fora(e, edges) { if (e.f <= e.t) cerr << e.f << "-" << e.t << " " << bel(e) << endl; } cerr << endl << endl; cerr << "!!query!! edge or not edge carefull!!" << endl;
#endif
} int dfs(int curr, int prev) { int sub = 1, max_sub = 0; heavy[curr] = -1;
forg_f(gi, g[curr]) { forg_f_init(g[curr]); int next = t; if (next != prev) { depth[next] = depth[curr] + 1; int sub_next = dfs(next, curr); sub += sub_next; if (max_sub < sub_next) max_sub = sub_next, heavy[curr] = next; } } return sub; } int t = 0;
#ifndef __CLION_IDE__
void dfs_hld(int v = 0) { vid[v] = subl[v] = t; t++; inv[subl[v]] = v; if (0 <= heavy[v]) { head[heavy[v]] = head[v]; dfs_hld(heavy[v]); }
forg_f(gi, g[v]){forg_f_init(g[v]); if (depth[v] < depth[t]) if (t != heavy[v]) { head[t] = t; dfs_hld(t); } subr[v] = t; }}
#endif//__CLION_IDE__
vector<signed> rmq_dep;
vi par_, depth, disv;
vi childs;
vi par_id_;//親への辺のidを持つ
vvi(ids_);//隣接で辺のidを持つ
public:
using undigraph<T>::g; using undigraph<T>::n; using undigraph<T>::edges;
int root;
//(f,t)と(t,f)は同じidを持ち、[0,n-1]でadd順に割り振られる
//部分木の [左端、右端) index
//部分木の辺に加算する場合
//add(subl[i],subr[i],x)
//add(sub[i],sub[i+1],-x)
vector<int> vid, head, heavy, inv, subl, subr;
tree(int n_, int root = 0) : undigraph<T>(n_), root(root) { n = n_; }
tree(int n_, int root, const vector<edge_<T>> &E) : undigraph<T>(n_), root(root) {n = n_;fora(e, E) { add(e.f, e.t, e.c); }}
// f < t
void add(int f, int t, T c = 1) {
#ifdef _DEBUG
if ((n % k5) == 0) {re("tree must resize");}
#endif
if (!(0 <= f && f < n && 0 <= t && t < n)) { cerr<<("tree add")<<endl; deb(f, t, c); ole(); }
g[f].emplace_back(f, t, c);
g[t].emplace_back(t, f, c);
edges.emplace_back(f, t, c);/*edgesを使わないなら消せる*/
edges.emplace_back(t, f, c);
}
void add_di(int f, int t, T c = 1) {
#ifdef _DEBUG
if ((n % k5) == 0) { re("tree must resize"); }
#endif
if (!(0 <= f && f < n && 0 <= t && t < n)) { cerr<<("tree add")<<endl; deb(f, t, c); ole(); } g[f].emplace_back(f, t, c); edges.emplace_back(f, t, c);/*edgesを使わないなら消せる*/ }
void root_change(int roo) { root = roo; precalc(); }
//葉になりえない頂点を根にする
void root_change_mid() {
#ifdef _DEBUG
#ifdef MESSAGE
message += "N>2 (mid)\n";
#endif
#endif
assert(n > 2); rep(i, n) { if (sz(g[i]) > 1) { root_change(i); return; } } }
int lca(int a, int b) { if (never)precalc(); int x = in[a]; int y = in[b]; if (x > y) { swap(x, y); } int pos = rmq.query(x, y + 1); return id_[pos]; }
int dis(int a, int b) { if (never)precalc(); int x = in[a]; int y = in[b]; if (x > y) { swap(x, y); } int pos = rmq.query(x, y + 1); int p = id_[pos]; return disv[a] + disv[b] - disv[p] * 2; }
int dep(int a) { if (never)precalc(); return disv[a]; }
int par(int a) { if (never)precalc(); return par_[a]; }
bool isleaf(int i) {if (never)precalc();return (sz(g[i]) == 1 && i != root);}
bool leaf(int i) { return isleaf(i); }
//vi child(int r) { vi res; res.push_back(r); queue<int> q; q.push(r); while (!q.empty()) { int i = q.front(); res.push_back(i); q.pop(); forg_f(gi, g[i]) { forg_f_init(g[i]); if (t != par(i))q.push(t); } } return res; }
vb child_ex(int r) { vb res(n); res[r] = true; queue<int> q; q.push(r); while (!q.empty()) { int i = q.front(); res[i] = true; q.pop(); forg_f(gi, g[i]) {forg_f_init(g[i]); if (t != par(i))q.push(t); } } return res; }
int dfs_count_subtree(int p, int i) { childs[i] = 1; fort_f(gi, g[i]) { fort_f_init(gi, g[i]); childs[i] += dfs_count_subtree(i, t); } return childs[i]; }
#define count_child count_subtree
int count_subtree(int f) { if (sz(childs) == 0) { if (never)precalc(); childs.resize(n); dfs_count_subtree(-1, root); } return childs[f]; }
//fからtの辺を切った時のtの大きさ
int count_subtree(int f, int t) { if (par(f) == t) { return n - count_subtree(f); } else { return count_subtree(t); } }
int size(int f, int t){return count_subtree(f, t);}
int size(){return n;}
vi path(int a, int b) { vi res; for_each_l(a, b, [&](int i) { res.push_back(i); }); return res; }
//idはedgesに使えない ↓edge(id)とする
//pathに含まれる辺のid達を返す
vi pathe(int a,int b){
#ifdef _DEBUG
#ifdef MESSAGE
static bool was = 0;if(!was)message+="can't edges[id]. must edge(id)\n";was=1;
#endif
#endif
if(sz(par_id_)==0){ ids_.resize(n); par_id_.resize(n); rep(i,0,sz(edges),2){ ids_[edges[i].f].emplace_back(i>>1); ids_[edges[i].t].emplace_back(i>>1); } if(never)precalc();/*par_を呼ぶため*/ rep(i, n){ int pa = par_[i]; forg_f(gi, g[i]){ forg_f_init(g[i]); if(t==pa){ par_id_[i] = ids_[i][gi]; } } } } int u = lca(a,b); vi res; if (a != u) { do { res.emplace_back(par_id_[a]); a = par_[a]; } while (a != u); } vi rev; if (b != u) { do { rev.emplace_back(par_id_[b]); b = par_[b]; } while (b != u); } rer(i,sz(rev)-1){ res.emplace_back(rev[i]); } return res;
}
//親の辺のidを返す
int par_id(int i){if(sz(par_id_)==0){pathe(0,0);}return par_id_[i];}
//fのi番目の辺のidを返す
int ids(int f,int i) {if(sz(ids_)==0){pathe(0,0);}return ids_[f][i];}
//idから辺を返す
edge_<T> edge(int id){return edges[id<<1];}
/*O(N) hldを使わず木を普通にたどる liteの意*/
void for_each_l(int u, int v, function<void(int)> fnode) { int r = lca(u, v); while (u != r) { fnode(u); u = par_[u]; } fnode(r); vi a; while (v != r) { a.push_back(v); v = par_[v]; } while(sz(a)){ fnode(a.back()); a.pop_back(); } }
void for_each_edge_l(int u, int v, function<void(edge_<int> &)> fedge) { int r = lca(u, v); while (u != r) { forg_f(gi, g[u]) {forg_f_init(g[u]); if (t == par_[u]) { fedge(g[u][gi]); u = par_[u]; break; } } } vector<edge_<int>> qs; while (v != r) { forg_f(gi, g[v]) { forg_f_init(g[v]); if (t == par_[v]) { qs.push_back(g[v][gi]); v = par_[v]; break; } } } while(sz(qs)){ fedge(qs.back()); qs.pop_back(); } }
//Fは半開 (u,v)は木の頂点
//中ではhldの頂点を見るため、seg木のupdateはhldのindexで行なう
void for_each_/*[l,r)*/(int u, int v, const function<void(int, int)> &f) { if (never_hld)hld_build(); while (1) { if (vid[u] > vid[v]) swap(u, v); int l = max(vid[head[v]], vid[u]); int r = vid[v] + 1; f(l, r); if (head[u] != head[v]) v = par_[head[v]]; else break; } }
void for_each_edge/*[l,r) O(log(N)) 辺を頂点として扱っている 上と同じ感じで使える*/(int u, int v, const function<void(int, int)> &f) { if (never_hld)hld_build(); while (1) { if (vid[u] > vid[v]) swap(u, v); if (head[u] != head[v]) { int l = vid[head[v]]; int r = vid[v] + 1; f(l, r); v = par_[head[v]]; } else { if (u != v) { int l = vid[u] + 1; int r = vid[v] + 1; f(l, r); } break; } } }
int bel(int v) { /*hld内での頂点番号を返す*/ if (never_hld)hld_build();return vid[v];}
//下の頂点に辺のクエリを持たせている
int bel(int f, int t) { /*辺のクエリを扱うときどの頂点に持たせればいいか(vidを返すのでそのままupd出来る)*/ if (never_hld)hld_build();return depth[f] > depth[t] ? vid[f] : vid[t];}
int bel(edge_<T> &e) { /*辺のクエリを扱うときどの頂点に持たせればいいか(vidを返すのでそのままupd出来る)*/ if (never_hld)hld_build();return depth[e.f] > depth[e.t] ? vid[e.f] : vid[e.t];}
template<class ... U> int operator()(U ... args) { return bel(args...); }
//path l -> r += v
template<class S> void seg_add(S &seg, int lhei, int rhei, int v) {for_each_(lhei, rhei, [&](int l, int r) { seg.add(l, r, v); });}
template<class S> void seg_update(S &seg, int lhei, int rhei, int v) {for_each_(lhei, rhei, [&](int l, int r) { seg.update(l, r, v); });}
template<class S> T seg_get(S &seg, int lhei, int rhei) { T res = seg.e; for_each_(lhei, rhei, [&](int l, int r) { res = seg.f(res, seg.get(l, r)); }); return res; }
template<class S> void seg_add_edge(S &seg, int lhei, int rhei, int v) { for_each_edge(lhei, rhei, [&](int l, int r) { seg.add(l, r, v); }); }
template<class S> void seg_update_edge(S &seg, int lhei, int rhei, int v) { for_each_edge(lhei, rhei, [&](int l, int r) { seg.update(l, r, v); }); }
template<class S> T seg_get_edge(S &seg, int lhei, int rhei) { T res = seg.e; for_each_edge(lhei, rhei, [&](int l, int r) { res = seg.f(res, seg.get(l, r)); }); return res; }
//単体 edgeは上で処理できる
template<class S> void seg_add(S &seg, int i, int v) { seg.add(bel(i), v); }
template<class S> void seg_update(S &seg, int i, int v) { seg.update(bel(i), v); }
template<class S> T seg_get(S &seg, int i) { return seg[i]; }
template<class S> void seg_del(S &seg, int i) { seg.del(bel(i)); }
//部分木iに対するクエリ
template<class S> void seg_add_sub(S &seg, int i, int v) {if (never_hld)hld_build();seg.add(subl[i], subr[i], v);}
template<class S> void seg_update_sub(S &seg, int i, int v) {if (never_hld)hld_build();seg.update(subl[i], subr[i], v);}
template<class S> T seg_get_sub(S &seg, int i, int v) {if (never_hld)hld_build();return seg.get(subl[i], subr[i], v);}
template<class S> void seg_add_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/seg.add(subl[i] + 1, subr[i], v);}
template<class S> void seg_update_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/seg.update(subl[i] + 1, subr[i], v);}
template<class S> T seg_get_sub_edge(S &seg, int i, int v) {if (never_hld)hld_build();/*iの上の辺が数えられてしまうため、i+1から*/return seg.get(subl[i] + 1, subr[i], v);}
};
//@snippet
//グリッド上のgraph
//grid_graph
//区間に辺を貼れるグラフ
//seg_graph
#define getid_2(h, w) ((h) * (W) + (w))
#define getid_1(p) ((p).first * W + (p).second)
#define o_getid(a,b,name,...) name
#define getid(...) o_getid(__VA_ARGS__, getid_2, getid_1) (__VA_ARGS__)
//forg基本
template<class T> struct forg_edge_body {
vector<edge_<T>> &edges;
int i;
explicit forg_edge_body(int i, vector<edge_<T>> &edges): i(i), edges(edges) {}
auto operator++() {i++;}
auto operator*() {
return tuple<int, int, int, T>(i, edges[i].f, edges[i].t, edges[i].c);
}
template<class U>auto operator!=(const U& rhs){return i != rhs.i;}
};
template<class T> struct fort_edge_body {
vector<edge_<T>> &edges; int gi, ci; int par; void can_gi() { while (gi < sz(edges) && edges[gi].t == par) { gi++; } } explicit fort_edge_body(int i, int par, vector<edge_<T>> &edges) : gi(i), ci(i), par(par), edges(edges) { can_gi(); } auto operator++() { ci++; gi++; can_gi(); }
auto operator*() {
return tuple<int, int, int, T>(ci, edges[gi].f, edges[gi].t, edges[gi].c);
}
template<class U> auto operator!=(const U &rhs) { return gi != rhs.gi; }
};
template<class T> struct forg_edge {
vector<edge_<T>> &edges;
forg_edge_body<T> endp;
forg_edge(vector<edge_<T>> &edges) : edges(edges), endp(sz(edges), edges) {}
auto begin() { return forg_edge_body<T>(0, edges); }
auto end() { return endp; }
};
template<class T> struct fort_edge {
vector<edge_<T>> &edges;
fort_edge_body<T> endp;
int p;
fort_edge(int p, vector<edge_<T>> &edges) : p(p), edges(edges), endp(sz(edges), p, edges) {}
auto begin() { return fort_edge_body<T>(0, p, edges); }
auto end() { return endp; }
};
/*@formatter:off*/
/*@formatter:off*/
#define forg(gi, edges) for(auto[gi, f, t, c] : forg_edge(edges))
#define fort(ci, edges) for(auto[ci, f, t, c] : fort_edge(p, edges))
template<class T> string deb_tos(digraph<T>& g){ stringstream ss; ss<<g.n<<endl; rep(i, g.n){ ss<<i<<" -> "; vi ts; forg(gi, g[i])ts += t; rep(i, sz(ts)-1){ ss<<ts[i]<<", "; } if(sz(ts))ss<<ts[sz(ts)-1]; ss<<endl; } return ss.str();}
template<class T> string deb_tos(undigraph<T>& g){ stringstream ss; ss<<g.n<<endl; rep(i, g.n){ ss<<i<<" -> "; vi ts; forg(gi, g[i]){ if(i <= t)ts += t; } rep(i, sz(ts)-1){ ss<<ts[i]<<", "; } if(sz(ts))ss<<ts[sz(ts)-1]; ss<<endl; } return ss.str();}
//@出力
template<class T> ostream &operator<<(ostream &os, digraph<T> &g) { os << endl << g.n << " " << sz(g.edges) << endl; fore(gi, g.edges) { os << f << " " << t << " " << c << endl; } return os;}template<class T> ostream &operator<<(ostream &os, undigraph<T> &g) { os << endl << g.n << " " << sz(g.edges) / 2 << endl; fore(gi, g.edges){ if (f < t)os << f << " " << t << " " << c << endl; } return os;}
#define edge edge_
//undigraphはunionfindを内蔵しているので
//same, sizeとeszieが使える
/*@formatter:on*/}
//子たちをマージしてから親に代入する
//・向いている問題
// iを根とする部分木の数
// 子について、その部分木と空の場合のdp[child]+1通りあるため
// (dp[child]+1)を掛けていけば良く、子だけでマージできるreroot_merge_applyが最適
////verify
//F - Distributing Integers :ABC160
//https://atcoder.jp/contests/abc160/tasks/abc160_f
//D - Driving on a Tree :square869120Contest #4
//https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_d
//G - Vertex Deletion
//ABC223 https://atcoder.jp/contests/abc223/tasks/abc223_g
// 参考
// https://null-mn.hatenablog.com/entry/2020/04/14/124151
// 辺のコストはとりあえずintのみとした
template<typename Monoid, typename EDGE, Monoid (*attract)(const Monoid &, const EDGE &), Monoid(*merge)(const Monoid &, const Monoid &), Monoid(*apply)(const Monoid &, int), Monoid(*leaf)(int), Monoid(*e_merge)()>
class reroot_merge_apply {
int N;
tree<int> G;
vector<vector<Monoid>> dp;
vector<Monoid> res;
// dp_v = apply(merge(att(dp_c1,edge1), att(dp_c2,edge2), ..., att(dp_ck,edgek)), v)
Monoid e; // identity of merge
public :
vector<Monoid> dp1;
reroot_merge_apply() {}
reroot_merge_apply(const tree<int> &g) : G(g), N(g.n), e(e_merge()) {
dp.resize(N);
for (int i = 0; i < N; ++i) dp[i].resize(G[i].size());
dp1.resize(N);
}
pair<vector<Monoid>, vector<Monoid>> solve() {
res.resize(N);
dfs1(-1, 0);
dfs2(-1, 0, e);
return {dp1, res};
}
private:
Monoid dfs1(int p, int v) {
Monoid res = e;
bool update = false;
for (int i = 0, en = G[v].size(); i < en; ++i) {
if (G[v][i].t == p) continue;
update = true;
dp[v][i] = dfs1(v, G[v][i].t);
res = merge(res, attract(dp[v][i], G[v][i]));
}
return dp1[v] = update ? apply(res, v) : leaf(v);
/* return apply(res, v);*/
}
void dfs2(int p, int v, Monoid from_par) {
for (int i = 0, en = G[v].size(); i < en; ++i) {
if (G[v][i].t == p) {
dp[v][i] = from_par;
break;
}
}
vector<Monoid> pR(G[v].size() + 1);
pR[G[v].size()] = e;
for (int i = G[v].size(); i > 0; --i)
pR[i - 1] = merge(pR[i], attract(dp[v][i - 1], G[v][i - 1]));
res[v] = apply(pR[0], v);
Monoid pL = e;
for (int i = 0, en = G[v].size(); i < en; ++i) {
if (G[v][i].t != p) {
Monoid val = merge(pL, pR[i + 1]);
dfs2(v, G[v][i].t, en == 1 ? leaf(v) : apply(val, v));
}
pL = merge(pL, attract(dp[v][i], G[v][i]));
}
}
};
int sa, sb;//部分木のサイズを持つ
using Monoid = bool;//まとめる型
using EDGE = edge_<int>;
// dp_v = apply(merge(att(dp_c1,edge1), att(dp_c2,edge2), ..., att(dp_ck,edgek)), v)
//子の値を辺ed(f->t)で引っ張る
//例1 iを根とする部分木の個数(子の部分木の個数+1(空) を掛ければいい)
//attract = dp_v + 1
//merge = a * b
//apply = a
//trueなら勝ち
//マージする時の単位元
Monoid e_merge() {
return false;
}
//子をマージできる形に変換する(辺で引っ張る(f, tでtが子))
Monoid attract_child(const Monoid &a, const EDGE &ed) {
return a;
}
//attractの結果達をマージする
Monoid merge_child(const Monoid &a, const Monoid &b) {
return a || b;
}
//applyはマージした結果を親に代入する時の処理
Monoid apply_root(const Monoid &a, int node) {
return !a;
}
Monoid leaf(int node) {
return true;
}
/*@formatter:off*/
pair<Monoid, signed> e_cou() { return pair<Monoid, signed>(e_merge(), 0); }
pair<Monoid, signed> attract_cou(const pair<Monoid, signed> &a, const EDGE &ed) {return pair<Monoid, signed>(attract_child(a.first, ed), a.second);}
pair<Monoid, signed> merge_cou(const pair<Monoid, signed> &a, const pair<Monoid, signed> &b) {sa = a.second;sb = b.second;return pair<Monoid, signed>(merge_child(a.first, b.first), a.second + b.second);}
pair<Monoid, signed> apply_cou(const pair<Monoid, signed> &a, int node) { return pair<Monoid, signed>(apply_root(a.first, node), a.second + 1);/*根(自分)をマージする操作なので+1*/}
pair<Monoid, signed> leaf_cou(int node) {return pair<Monoid, signed>(leaf(node), 1);/*根(自分)をマージする操作なので+1*/}
pair<vector<Monoid>, vector<Monoid>> reroot(const tree<int> &g) {reroot_merge_apply<Monoid, EDGE, attract_child, merge_child, apply_root, leaf, e_merge> rero(g);return rero.solve();}
//部分木のサイズにsa, sbでアクセス出来る
pair<vector<Monoid>, vector<Monoid>> reroot_size(const tree<int> &g) {reroot_merge_apply<pair<Monoid, signed>, EDGE, attract_cou, merge_cou, apply_cou, leaf_cou, e_cou> rero(g);auto[dp1, dp2] = rero.solve();vector<Monoid> res1;/*deb*/vector<Monoid> res2;for (auto&[k, v] : dp1) { res1.emplace_back(k); }for (auto&[k, v] : dp2) { res2.emplace_back(k); }return {res1, res2};}
/*@formatter:on*/
//親をサイズ1のnodeとして、そこに子をマージしていく
//・向いている問題
// 白と黒で黒が隣り合ってはいけない塗り分け系等
//reroot_apply_merge
//デバッグのため、1回目のdpも返す
//auto[dp1, res] = reroot(g);
signed main() {
int N;
cin >> N;
tree<> g(N);
g.ing(N, N - 1);
auto[dp1, ret] = reroot(g);
deb(dp1);
deb(ret);
/* rep(i, N){
cout << i<<"dp"<<dp1[i] << endl;
}
rep(i, N){
cout << i<<" ret "<<ret[i] << endl;
}*/
int cou = 0;
for (auto r : ret) {
if (r)cou++;
}
cout << cou << endl;
rep(i, N) {
if (ret[i]) {
cout << (i + 1) << endl;
}
}
return 0;
}