結果
問題 | 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
|
実行時間 | 163 ms / 2,000 ms |
コード長 | 58,618 bytes |
コンパイル時間 | 2,843 ms |
コンパイル使用メモリ | 218,916 KB |
実行使用メモリ | 41,664 KB |
最終ジャッジ日時 | 2024-09-15 13:50:42 |
合計ジャッジ時間 | 6,078 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 3 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 80 ms
26,460 KB |
testcase_08 | AC | 36 ms
15,428 KB |
testcase_09 | AC | 47 ms
17,620 KB |
testcase_10 | AC | 33 ms
14,396 KB |
testcase_11 | AC | 152 ms
39,480 KB |
testcase_12 | AC | 152 ms
39,652 KB |
testcase_13 | AC | 142 ms
38,508 KB |
testcase_14 | AC | 141 ms
38,496 KB |
testcase_15 | AC | 153 ms
40,812 KB |
testcase_16 | AC | 152 ms
41,064 KB |
testcase_17 | AC | 163 ms
41,664 KB |
testcase_18 | AC | 127 ms
40,136 KB |
testcase_19 | AC | 121 ms
40,128 KB |
testcase_20 | AC | 111 ms
38,868 KB |
testcase_21 | AC | 104 ms
36,980 KB |
20evil_special_uni1.txt | AC | 133 ms
40,612 KB |
20evil_special_uni2.txt | AC | 128 ms
38,628 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; }