結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2021-12-18 18:14:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 138 ms / 2,000 ms |
コード長 | 58,618 bytes |
コンパイル時間 | 2,421 ms |
コンパイル使用メモリ | 210,892 KB |
最終ジャッジ日時 | 2025-01-27 03:21:03 |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#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 >= 201402Lusing 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>* = nullptrtemplate<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 longusing 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 10101010const 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=-1void 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 _DEBUGcerr << "ole" << endl;exit(0);#endifstring 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_graphstruct 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_UNIONFINDtemplate<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); } }#elseexplicit 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 < tvoid 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_UNIONFINDuf.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_UNIONFINDusing 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_pathtemplate<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])) { intm = 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; TinitValue = 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(unsignedlong 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; TinitValue = 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//たどり着けない := linftemplate<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//たどり着けない := -linftemplate<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 (signedj = 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 _DEBUGif (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 _DEBUGif (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 < tvoid add(int f, int t, T c = 1) {#ifdef _DEBUGif ((n % k5) == 0) {re("tree must resize");}#endifif (!(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 _DEBUGif ((n % k5) == 0) { re("tree must resize"); }#endifif (!(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 MESSAGEmessage += "N>2 (mid)\n";#endif#endifassert(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); } intpos = 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); } intpos = 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()) { inti = 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_subtreeint 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 { returncount_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 MESSAGEstatic bool was = 0;if(!was)message+="can't edges[id]. must edge(id)\n";was=1;#endif#endifif(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 += vtemplate<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 mergepublic :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;}