結果
| 問題 | No.763 Noelちゃんと木遊び |
| ユーザー |
 taotao54321
|
| 提出日時 | 2020-02-09 14:49:31 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 50 ms / 2,000 ms |
| コード長 | 51,906 bytes |
| コンパイル時間 | 2,945 ms |
| コンパイル使用メモリ | 253,868 KB |
| 実行使用メモリ | 20,364 KB |
| 最終ジャッジ日時 | 2024-10-01 05:56:57 |
| 合計ジャッジ時間 | 4,513 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
20,364 KB |
| testcase_01 | AC | 17 ms
7,680 KB |
| testcase_02 | AC | 36 ms
13,440 KB |
| testcase_03 | AC | 24 ms
10,112 KB |
| testcase_04 | AC | 18 ms
8,064 KB |
| testcase_05 | AC | 22 ms
9,984 KB |
| testcase_06 | AC | 46 ms
15,488 KB |
| testcase_07 | AC | 48 ms
15,232 KB |
| testcase_08 | AC | 29 ms
10,496 KB |
| testcase_09 | AC | 19 ms
8,064 KB |
| testcase_10 | AC | 8 ms
5,248 KB |
| testcase_11 | AC | 50 ms
15,744 KB |
| testcase_12 | AC | 43 ms
14,208 KB |
| testcase_13 | AC | 43 ms
14,208 KB |
| testcase_14 | AC | 36 ms
13,056 KB |
| testcase_15 | AC | 24 ms
10,240 KB |
| testcase_16 | AC | 6 ms
5,248 KB |
| testcase_17 | AC | 24 ms
10,112 KB |
| testcase_18 | AC | 46 ms
15,616 KB |
| testcase_19 | AC | 47 ms
14,464 KB |
| testcase_20 | AC | 42 ms
14,336 KB |
ソースコード
/**
*
*/
#define ASSERT_LV 1
// header {{{
#ifndef ASSERT_LV
# define ASSERT_LV 1
#endif
#if ASSERT_LV == 0
# define NDEBUG
#endif
#if defined(__GNUC__) && !defined(__clang__)
#include <bits/stdc++.h>
#else
#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>
//#include <cwchar>
//#include <cwctype>
#if __cplusplus >= 201103L
//#include <ccomplex>
#include <cfenv>
#include <cinttypes>
//#include <cstdalign>
//#include <cstdbool>
#include <cstdint>
//#include <ctgmath>
//#include <cuchar>
#endif
#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
#if __cplusplus >= 201402L
//#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
//#include <charconv>
//#include <execution>
//#include <filesystem>
#include <optional>
//#include <memory_resource>
#include <string_view>
#include <variant>
#endif
#endif
using namespace std;
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128;
using u128 = unsigned __int128;
#endif
using f32 = float;
using f64 = double;
using f80 = long double;
template<class T> constexpr T PROCON_INF();
template<> constexpr i32 PROCON_INF<i32>() { return 1'010'000'011; }
template<> constexpr i64 PROCON_INF<i64>() { return INT64_C(1'010'000'000'000'000'017); }
template<> constexpr f32 PROCON_INF<f32>() { return 1e19F; }
template<> constexpr f64 PROCON_INF<f64>() { return 1e100; }
template<> constexpr f80 PROCON_INF<f80>() { return 1e100L; }
// }}}
using Int = i64;
using Real = f80;
constexpr Int MOD = 1'000'000'007;
//constexpr Int MOD = 998'244'353;
constexpr Real EPS = Real(1e-10L);
constexpr int COUT_PREC = 15;
constexpr bool COUT_AUTOFLUSH = false;
// procon {{{
static_assert(is_same<Int,i64>::value || is_same<Int,i32>::value, "");
static_assert(is_same<Real,f80>::value || is_same<Real,f64>::value || is_same<Real,f32>::value, "");
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
#define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr
#define ASSERT(expr...) assert((expr))
#if defined(PROCON_LOCAL) || ASSERT_LV >= 2
# define ASSERT_LOCAL(expr...) assert((expr))
#else
# define ASSERT_LOCAL(expr...)
#endif
constexpr Int INF = PROCON_INF<Int>();
constexpr Real FINF = PROCON_INF<Real>();
constexpr Real PI = Real(3.141592653589793238462643383279502884197L);
template<class T> constexpr T SQRT_MAX();
template<> constexpr i32 SQRT_MAX<i32>() { return 46340; }
template<> constexpr i64 SQRT_MAX<i64>() { return INT64_C(3037000499); }
template<class T, SFINAE(is_signed<T>::value)>
constexpr T ABS(T x) noexcept {
return x < 0 ? -x : x;
}
constexpr bool LT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs < rhs-eps; }
constexpr bool GT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs > rhs+eps; }
constexpr bool EQ_EPS(Real lhs, Real rhs, Real eps=EPS) { return ABS(lhs-rhs) <= eps; }
constexpr bool EQ_EXACT(Real lhs, Real rhs) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
return lhs == rhs;
#pragma GCC diagnostic pop
}
#define FOR(i, start, end) for(Int i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define LOOP(n) REP(CPP_CAT(macro_loop_counter,__COUNTER__), n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\
auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\
auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\
return (f)(iiii, jjjj, ## __VA_ARGS__);\
})(c,l,r))
#define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })
template<class C>
constexpr Int SIZE(const C& c) noexcept { return Int(c.size()); }
template<class T, size_t N>
constexpr Int SIZE(const T (&)[N]) noexcept { return Int(N); }
constexpr bool is_odd (Int x) { return x%2 != 0; }
constexpr bool is_even(Int x) { return x%2 == 0; }
constexpr Int PARITY(Int x) { return x%2==0 ? 0 : 1; }
template<class T>
constexpr Int CMP(T x, T y) noexcept { return (y<x) - (x<y); }
template<class T>
constexpr Int SGN(T x) noexcept { return CMP(x,T(0)); }
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_integral<T1>::value &&
is_integral<T2>::value &&
is_signed<T1>::value != is_unsigned<T2>::value
)>
constexpr auto MAX(T1 x, T2 y, Comp comp={}) {
return max<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_floating_point<T1>::value &&
is_floating_point<T2>::value
)>
constexpr auto MAX(T1 x, T2 y, Comp comp={}) {
return max<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T, class Comp=less<>>
constexpr const T& MAX(const T& x, const T& y, Comp comp={}) {
return max(x, y, comp);
}
template<class T, class Comp=less<>>
constexpr T MAX(initializer_list<T> ilist, Comp comp={}) {
return max(ilist, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_integral<T1>::value &&
is_integral<T2>::value &&
is_signed<T1>::value != is_unsigned<T2>::value
)>
constexpr auto MIN(T1 x, T2 y, Comp comp={}) {
return min<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_floating_point<T1>::value &&
is_floating_point<T2>::value
)>
constexpr auto MIN(T1 x, T2 y, Comp comp={}) {
return min<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T, class Comp=less<>>
constexpr const T& MIN(const T& x, const T& y, Comp comp={}) {
return min(x, y, comp);
}
template<class T, class Comp=less<>>
constexpr T MIN(initializer_list<T> ilist, Comp comp={}) {
return min(ilist, comp);
}
template<class T, class U, class Comp=less<>>
constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept {
if(comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
template<class T, class U, class Comp=less<>>
constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept {
if(comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
template<class BinaryFunc, class UnaryFunc>
auto ON(BinaryFunc&& bf, UnaryFunc&& uf) {
return [bf=forward<BinaryFunc>(bf),uf=forward<UnaryFunc>(uf)](const auto& x, const auto& y) {
return bf(uf(x), uf(y));
};
}
template<class F>
auto LT_ON(F&& f) {
return ON(less<>{}, forward<F>(f));
}
template<class F>
auto GT_ON(F&& f) {
return ON(greater<>{}, forward<F>(f));
}
template<class F>
auto NOT_FN(F&& f) {
return [f=forward<F>(f)](auto&&... args) -> bool { return !f(forward<decltype(args)>(args)...); };
}
struct IDENTITY {
using is_transparent = void;
template<class T>
constexpr decltype(auto) operator()(T&& x) const { return forward<T>(x); }
};
// ビット演算 {{{
// 引数は [-INF,INF] のみ想定
constexpr Int BIT_I(Int i) {
return Int(1) << i;
}
constexpr Int BIT_I_1(Int i) {
return BIT_I(i) - 1;
}
constexpr Int BIT_GET(Int x, Int i) {
return x & BIT_I(i);
}
constexpr bool BIT_TEST(Int x, Int i) {
return BIT_GET(x,i) != 0;
}
constexpr Int BIT_SET(Int x, Int i) {
return x | BIT_I(i);
}
constexpr Int BIT_CLEAR(Int x, Int i) {
return x & ~BIT_I(i);
}
constexpr Int BIT_FLIP(Int x, Int i) {
return x ^ BIT_I(i);
}
constexpr Int BIT_ASSIGN(Int x, Int i, bool b) {
return b ? BIT_SET(x,i) : BIT_CLEAR(x,i);
}
/*constexpr*/ Int BIT_COUNT_LEADING_ZEROS(Int x) {
if(is_same<Int,i64>::value)
return x==0 ? 64 : __builtin_clzll(u64(x));
else if(is_same<Int,i32>::value)
return x==0 ? 32 : __builtin_clz(u32(x));
ASSERT(false);
}
/*constexpr*/ Int BIT_COUNT_TRAILING_ZEROS(Int x) {
if(is_same<Int,i64>::value)
return x==0 ? 64 : __builtin_ctzll(u64(x));
else if(is_same<Int,i32>::value)
return x==0 ? 32 : __builtin_clz(u32(x));
ASSERT(false);
}
/*constexpr*/ Int BIT_COUNT_ONES(Int x) {
if(is_same<Int,i64>::value)
return __builtin_popcountll(u64(x));
else if(is_same<Int,i32>::value)
return __builtin_popcount(u32(x));
ASSERT(false);
}
// 1の個数が奇数なら1, 偶数なら0を返す
/*constexpr*/ Int BIT_PARITY(Int x) {
if(is_same<Int,i64>::value)
return __builtin_parityll(u64(x));
else if(is_same<Int,i32>::value)
return __builtin_parity(u32(x));
ASSERT(false);
}
// X ⊆ {0,1,...,n-1}, |X| = k なる部分集合 X を昇順に列挙する
// comb(n,k) 個
//
// ```
// Int x = BIT_I_1(3);
// do {
// // ...
// } while(BIT_NEXT_SET_SIZED(x, 10));
// ```
/*constexpr*/ bool BIT_NEXT_SET_SIZED(Int& x, Int n) {
if(x == 0) return false;
Int t = (x|(x-1)) + 1;
x = t | ((~t&(t-1)) >> (BIT_COUNT_TRAILING_ZEROS(x)+1));
return x < BIT_I(n);
}
// 集合 Y の部分集合 X を昇順に列挙する
// 2^|Y| 個
//
// ```
// Int y = 0b10101;
// Int x = 0;
// do {
// // ...
// } while(BIT_NEXT_SUBSET(x, y));
// ```
constexpr bool BIT_NEXT_SUBSET(Int& x, Int y) {
if(x == y) return false;
x = (x-y) & y;
return true;
}
// 集合 Y の部分集合 X を降順に列挙する
// 2^|Y| 個
//
// ```
// Int y = 0b10101;
// Int x = y;
// do {
// // ...
// } while(BIT_PREV_SUBSET(x, y));
// ```
constexpr bool BIT_PREV_SUBSET(Int& x, Int y) {
if(x == 0) return false;
x = (x-1) & y;
return true;
}
// 集合 Y を包含する集合 X ⊆ {0,1,...,n-1} を昇順に列挙する
// 2^(n-|Y|) 個
//
// ```
// Int y = 0b00010101;
// Int x = y;
// do {
// // ...
// } while(BIT_NEXT_SUPERSET(x, 8, y));
// ```
constexpr bool BIT_NEXT_SUPERSET(Int& x, Int n, Int y) {
x = (x+1) | y;
return x < BIT_I(n);
}
// }}}
// lo:OK, hi:NG
template<class Pred>
/*constexpr*/ Int bisect_integer(Int lo, Int hi, Pred pred) {
ASSERT(lo < hi);
while(lo+1 < hi) {
Int mid = (lo+hi) / 2;
if(pred(mid))
lo = mid;
else
hi = mid;
}
return lo;
}
template<class Pred>
/*constexpr*/ Real bisect_real(Real lo, Real hi, Pred pred, Real eps=EPS) {
ASSERT_LOCAL(!GT_EPS(lo,hi,eps));
if(lo > hi) swap(lo, hi);
while(!EQ_EPS(lo,hi,eps)) {
Real mid = (lo+hi) / 2;
if(pred(mid))
lo = mid;
else
hi = mid;
}
return lo;
}
template<class Monoid>
/*constexpr*/ Monoid fastpow(const Monoid& x, Int e, const Monoid& unity) {
ASSERT(e >= 0);
Monoid res = unity;
Monoid cur = x;
while(e > 0) {
if(e & 1)
res *= cur;
cur *= cur;
e >>= 1;
}
return res;
}
/*constexpr*/ Int ipow(Int x, Int e) {
return fastpow<Int>(x,e,1);
}
/*constexpr*/ Int sqrt_floor(Int x) {
ASSERT(x >= 0);
Int lo = 0;
Int hi = MIN(x/2+2, SQRT_MAX<Int>()+1);
return bisect_integer(lo, hi, [x](Int r) { return r*r <= x; });
}
/*constexpr*/ Int sqrt_ceil(Int x) {
Int r = sqrt_floor(x);
return r*r == x ? r : r+1;
}
/*constexpr*/ Int log2_ceil(Int x) {
ASSERT(x > 0);
if(is_same<Int,i64>::value)
return 64 - BIT_COUNT_LEADING_ZEROS(x-1);
else if(is_same<Int,i32>::value)
return 32 - BIT_COUNT_LEADING_ZEROS(x-1);
ASSERT(false);
}
/*constexpr*/ Int log2_floor(Int x) {
ASSERT(x > 0);
if(is_same<Int,i64>::value)
return 63 - BIT_COUNT_LEADING_ZEROS(x);
else if(is_same<Int,i32>::value)
return 31 - BIT_COUNT_LEADING_ZEROS(x);
ASSERT(false);
}
// x > 0
/*constexpr*/ Int pow2_ceil(Int x) {
return BIT_I(log2_ceil(x));
}
// x > 0
/*constexpr*/ Int pow2_floor(Int x) {
return BIT_I(log2_floor(x));
}
// Haskell の divMod と同じ
constexpr pair<Int,Int> divmod(Int a, Int b) {
Int q = a / b;
Int r = a % b;
if((b>0 && r<0) || (b<0 && r>0)) {
--q;
r += b;
}
return {q,r};
}
constexpr Int div_ceil(Int a, Int b) {
Int q = a / b;
Int r = a % b;
if((b>0 && r>0) || (b<0 && r<0))
++q;
return q;
}
constexpr Int div_floor(Int a, Int b) {
return divmod(a,b).first;
}
constexpr Int modulo(Int a, Int b) {
return divmod(a,b).second;
}
/*constexpr*/ Int align_ceil(Int x, Int align) {
ASSERT(align > 0);
return div_ceil(x,align) * align;
}
/*constexpr*/ Int align_floor(Int x, Int align) {
ASSERT(align > 0);
return div_floor(x,align) * align;
}
template<class InputIt, class BinaryOp>
auto FOLD(InputIt first, InputIt last,
typename iterator_traits<InputIt>::value_type init,
BinaryOp op)
{
for(; first != last; ++first)
init = op(move(init), *first);
return init;
}
template<class InputIt, class BinaryOp>
auto FOLD1(InputIt first, InputIt last, BinaryOp op) {
auto init = *first++;
return FOLD(first, last, init, op);
}
template<class InputIt>
auto SUM(InputIt first, InputIt last) {
return FOLD1(first, last, plus<>{});
}
template<class C>
void UNIQ(C& c) {
c.erase(ALL(unique,c), end(c));
}
template<class C>
void SORT_UNIQ(C& c) {
ALL(sort, c);
UNIQ(c);
}
[[noreturn]] void EXIT() {
cout.flush();
#ifdef PROCON_LOCAL
cerr.flush();
exit(0);
#else
_Exit(0);
#endif
}
// tuple {{{
template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>
void tuple_enumerate(tuple<TS...>&, F&&) {}
template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>
void tuple_enumerate(tuple<TS...>& t, F&& f) {
f(I, get<I>(t));
tuple_enumerate<I+1>(t, forward<F>(f));
}
template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>
void tuple_enumerate(const tuple<TS...>&, F&&) {}
template<Int I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>
void tuple_enumerate(const tuple<TS...>& t, F&& f) {
f(I, get<I>(t));
tuple_enumerate<I+1>(t, forward<F>(f));
}
// }}}
// container {{{
template<class T> struct is_container : false_type {};
template<class T, size_t N> struct is_container<array<T,N>> : true_type {};
template<class... Args> struct is_container<vector<Args...>> : true_type {};
template<class... Args> struct is_container<deque<Args...>> : true_type {};
template<class... Args> struct is_container<list<Args...>> : true_type {};
template<class... Args> struct is_container<forward_list<Args...>> : true_type {};
template<class... Args> struct is_container<set<Args...>> : true_type {};
template<class... Args> struct is_container<multiset<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_set<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_multiset<Args...>> : true_type {};
template<class... Args> struct is_container<map<Args...>> : true_type {};
template<class... Args> struct is_container<multimap<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_map<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_multimap<Args...>> : true_type {};
template<class T, class Enable=void>
struct ProconHash {
size_t operator()(const T& x) const noexcept {
return hash<T>{}(x);
}
};
template<class T>
size_t procon_hash_value(const T& x) noexcept {
return ProconHash<T>{}(x);
}
size_t procon_hash_combine(size_t h1, size_t h2) noexcept {
constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995);
constexpr int R = 47;
h2 *= M;
h2 ^= h2 >> R;
h2 *= M;
h1 ^= h2;
h1 *= M;
h1 += 0xe6546b64;
return h1;
}
template<class T1, class T2>
struct ProconHash<pair<T1,T2>> {
size_t operator()(const pair<T1,T2>& p) const noexcept {
size_t h1 = procon_hash_value(p.first);
size_t h2 = procon_hash_value(p.second);
return procon_hash_combine(h1, h2);
}
};
template<class... TS>
struct ProconHash<tuple<TS...>> {
size_t operator()(const tuple<TS...>& t) const noexcept {
size_t h = 0;
tuple_enumerate(t, [&h](Int, const auto& e) {
h = procon_hash_combine(h, procon_hash_value(e));
});
return h;
}
};
template<class C>
struct ProconHash<C,enable_if_t<is_container<C>::value>> {
size_t operator()(const C& c) const noexcept {
size_t h = 0;
for(const auto& e : c)
h = procon_hash_combine(h, procon_hash_value(e));
return h;
}
};
template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>
using HashSet = unordered_set<T,Hash,Eq>;
template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>
using HashMap = unordered_map<K,V,Hash,Eq>;
template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>
using HashMultiset = unordered_multiset<T,Hash,Eq>;
template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>
using HashMultimap = unordered_multimap<K,V,Hash,Eq>;
template<class T>
auto vec_make(Int n, T x) {
return vector<T>(n, x);
}
template<class T, class... Args, SFINAE(sizeof...(Args) >= 2)>
auto vec_make(Int n, Args... args) {
auto inner = vec_make<T>(args...);
return vector<decltype(inner)>(n, inner);
}
template<class T>
auto vec_reserve(Int cap) {
vector<T> res;
res.reserve(cap);
return res;
}
template<class T=Int>
auto vec_iota(Int n, T init={}) {
vector<Int> res(n);
ALL(iota, res, init);
return res;
}
template<class ForwardIt, class BinaryOp>
auto vec_scan(ForwardIt first, ForwardIt last,
typename iterator_traits<ForwardIt>::value_type init,
BinaryOp op)
{
using T = typename iterator_traits<ForwardIt>::value_type;
auto res = vec_reserve<T>(distance(first,last)+1);
res.emplace_back(init);
for(; first != last; ++first) {
init = op(move(init), *first);
res.emplace_back(init);
}
return res;
}
template<class ForwardIt>
auto vec_cum(ForwardIt first, ForwardIt last) {
using T = typename iterator_traits<ForwardIt>::value_type;
return vec_scan(first, last, T{}, plus<>{});
}
template<class T, class Comp, class Cont=vector<T>>
auto priority_queue_make(const Comp& comp, Cont&& cont={}) {
return priority_queue<T,remove_reference_t<Cont>,Comp>(comp, forward<Cont>(cont));
}
template<class T, class Comp>
auto priority_queue_reserve(const Comp& comp, Int cap) {
return priority_queue<T,vector<T>,Comp>(comp, vec_reserve<T>(cap));
}
template<class T, size_t N, size_t... NS>
struct ArrayType {
using type = array<class ArrayType<T,NS...>::type,N>;
};
template<class T, size_t N>
struct ArrayType<T,N> {
using type = array<T,N>;
};
template<class T, size_t... NS>
using Array = typename ArrayType<T,NS...>::type;
template<class T, size_t N>
T& array_at(Array<T,N>& ary, Int i) {
return ary[i];
}
template<class T, size_t N, size_t... NS, class... Args>
T& array_at(Array<T,N,NS...>& ary, Int i, Args... args) {
return array_at<T,NS...>(ary[i], args...);
}
template<class T, size_t N>
const T& array_at(const Array<T,N>& ary, Int i) {
return ary[i];
}
template<class T, size_t N, size_t... NS, class... Args>
const T& array_at(const Array<T,N,NS...>& ary, Int i, Args... args) {
return array_at<T,NS...>(ary[i], args...);
}
template<class T, class C>
T POP(stack<T,C>& stk) {
T x = stk.top(); stk.pop();
return x;
}
template<class T, class C>
T POP(queue<T,C>& que) {
T x = que.front(); que.pop();
return x;
}
template<class T, class C, class Comp>
T POP(priority_queue<T,C,Comp>& que) {
T x = que.top(); que.pop();
return x;
}
// }}}
// fixpoint {{{
template<class F>
class FixPoint {
public:
explicit constexpr FixPoint(F&& f) : f_(forward<F>(f)) {}
template<class... Args>
constexpr decltype(auto) operator()(Args&&... args) const {
return f_(*this, forward<Args>(args)...);
}
private:
F f_;
};
template<class F>
constexpr decltype(auto) FIX(F&& f) {
return FixPoint<F>(forward<F>(f));
}
template<class F, size_t... NS>
class FixPointMemo {
public:
explicit FixPointMemo(F&& f) : f_(forward<F>(f)) {}
template<class... Args>
decltype(auto) operator()(Args... args) const {
using R = decltype(f_(*this,args...));
static Array<bool,NS...> done {};
static Array<R,NS...> memo;
if(!array_at<bool,NS...>(done,args...)) {
array_at<R,NS...>(memo,args...) = f_(*this,args...);
array_at<bool,NS...>(done,args...) = true;
}
return array_at<R,NS...>(memo,args...);
}
private:
F f_;
};
template<size_t... NS, class F>
decltype(auto) FIXMEMO(F&& f) {
return FixPointMemo<F,NS...>(forward<F>(f));
}
// }}}
// math {{{
/*constexpr*/ Int GCD(Int a, Int b) noexcept {
/*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int {
if(bb == 0) return aa;
return self(bb, aa%bb);
});
return f_gcd(ABS(a), ABS(b));
}
/*constexpr*/ Int LCM(Int a, Int b) noexcept {
ASSERT(a != 0 && b != 0);
/*constexpr*/ auto f_gcd = FIX([](auto&& self, Int aa, Int bb) -> Int {
if(bb == 0) return aa;
return self(bb, aa%bb);
});
a = ABS(a);
b = ABS(b);
return a / f_gcd(a,b) * b;
}
/*constexpr*/ tuple<Int,Int,Int> EXTGCD(Int a, Int b) noexcept {
/*constexpr*/ auto impl = FIX([](auto&& self, Int aa, Int bb, Int& x, Int& y) -> Int {
if(bb == 0) {
x = 1; y = 0;
return aa;
}
Int g = self(bb, aa%bb, y, x);
y -= (aa/bb)*x;
return g;
});
Int x{},y{};
Int g = impl(ABS(a), ABS(b), x, y);
x *= SGN(a);
y *= SGN(b);
return make_tuple(g, x, y);
}
// }}}
// string {{{
char chr_digit(Int n) { return char('0'+n); }
Int ord_digit(char c) { return c-'0'; }
char chr_lower(Int n) { return char('a'+n); }
Int ord_lower(char c) { return c-'a'; }
char chr_upper(Int n) { return char('A'+n); }
Int ord_upper(char c) { return c-'A'; }
auto str_reserve(Int cap) {
string res;
res.reserve(cap);
return res;
}
// }}}
// input {{{
template<class T>
struct Integral1 {
static_assert(is_integral<T>::value && !is_same<T,bool>::value, "");
};
using Int1 = Integral1<Int>;
template<class T, class Enable=void>
struct Scan {
using R = T;
static R scan(istream& in) {
R res;
in >> res;
return res;
}
};
template<class T>
struct Scan<Integral1<T>> {
using R = T;
static R scan(istream& in) {
return Scan<R>::scan(in) - 1;
}
};
template<class T1, class T2>
struct Scan<pair<T1,T2>> {
using R1 = typename Scan<T1>::R;
using R2 = typename Scan<T2>::R;
using R = pair<R1,R2>;
static R scan(istream& in) {
R1 x = Scan<T1>::scan(in);
R2 y = Scan<T2>::scan(in);
return {x,y};
}
};
template<class T>
auto tuple_scan_impl(istream& in) {
return make_tuple(Scan<T>::scan(in));
}
template<class T, class... TS, SFINAE(sizeof...(TS) > 0)>
auto tuple_scan_impl(istream& in) {
auto head = make_tuple(Scan<T>::scan(in));
return tuple_cat(head, tuple_scan_impl<TS...>(in));
}
template<class... TS>
struct Scan<tuple<TS...>> {
using R = decltype(tuple_scan_impl<TS...>(cin));
static R scan(istream& in) {
return tuple_scan_impl<TS...>(in);
}
};
template<class T=Int>
auto RD() {
return Scan<T>::scan(cin);
}
template<class T=Int>
auto RD1() {
return RD<Integral1<T>>();
}
template<class T=Int>
auto RD_VEC(Int n) {
auto res = vec_reserve<typename Scan<T>::R>(n);
LOOP(n) {
res.emplace_back(RD<T>());
}
return res;
}
template<class T=Int>
auto RD1_VEC(Int n) {
return RD_VEC<Integral1<T>>(n);
}
template<class T=Int>
auto RD_VEC2(Int h, Int w) {
auto res = vec_reserve<vector<typename Scan<T>::R>>(h);
LOOP(h) {
res.emplace_back(RD_VEC<T>(w));
}
return res;
}
template<class T=Int>
auto RD1_VEC2(Int h, Int w) {
return RD_VEC2<Integral1<T>>(h, w);
}
// }}}
// output {{{
template<class T, class Enable=void>
struct Fmt {
static void fmt(ostream& out, const T& x) { out << x; }
};
template<class T>
void fmt_write(ostream& out, const T& x) {
Fmt<T>::fmt(out, x);
}
template<class T>
string FMT_STR(const T& x) {
ostringstream out;
fmt_write(out, x);
return out.str();
}
template<class... TS>
struct Fmt<tuple<TS...>> {
static void fmt(ostream& out, const tuple<TS...>& t) {
tuple_enumerate(t, [&out](Int i, const auto& e) {
if(i != 0) out << ' ';
fmt_write(out, e);
});
}
};
template<class T1, class T2>
struct Fmt<pair<T1,T2>> {
static void fmt(ostream& out, const pair<T1,T2>& p) {
return fmt_write(out, make_tuple(p.first,p.second));
}
};
template<class C>
struct Fmt<C,enable_if_t<is_container<C>::value>> {
static void fmt(ostream& out, const C& c) {
for(auto it = begin(c); it != end(c); ++it) {
if(it != begin(c)) out << ' ';
fmt_write(out, *it);
}
}
};
void PRINT() {}
template<class T, class... TS>
void PRINT(const T& x, const TS&... args) {
fmt_write(cout, x);
if(sizeof...(args) > 0) {
cout << ' ';
PRINT(args...);
}
}
template<class... TS>
void PRINTLN(const TS&... args) {
PRINT(args...);
cout << '\n';
}
// }}}
// debug {{{
template<class T, class Enable=void>
struct Dbg {
static void dbg(ostream& out, const T& x) { out << x; }
};
template<class T>
void dbg_write(ostream& out, const T& x) {
Dbg<T>::dbg(out, x);
}
template<class T>
string DBG_STR(const T& x) {
ostringstream out;
dbg_write(out, x);
return out.str();
}
template<>
struct Dbg<Int> {
static void dbg(ostream& out, Int x) {
if(x == INF)
out << "INF";
else if(x == -INF)
out << "-INF";
else
out << x;
}
};
template<>
struct Dbg<Real> {
static void dbg(ostream& out, Real x) {
if(EQ_EXACT(x, FINF))
out << "FINF";
else if(EQ_EXACT(x, -FINF))
out << "-FINF";
else
out << x;
}
};
template<class T, size_t N>
struct Dbg<T[N]> {
static void dbg(ostream& out, const T (&ary)[N]) {
out << "[";
REP(i, N) {
if(i != 0) out << ",";
dbg_write(out, ary[i]);
}
out << "]";
}
};
template<size_t N>
struct Dbg<char[N]> {
static void dbg(ostream& out, const char (&s)[N]) {
out << s;
}
};
template<class... TS>
struct Dbg<tuple<TS...>> {
static void dbg(ostream& out, const tuple<TS...>& t) {
out << "(";
tuple_enumerate(t, [&out](Int i, const auto& e) {
if(i != 0) out << ",";
dbg_write(out, e);
});
out << ")";
}
};
template<class T1, class T2>
struct Dbg<pair<T1,T2>> {
static void dbg(ostream& out, const pair<T1,T2>& p) {
return dbg_write(out, make_tuple(p.first,p.second));
}
};
template<class C>
struct Dbg<C,enable_if_t<is_container<C>::value>> {
static void dbg(ostream& out, const C& c) {
out << "[";
for(auto it = begin(c); it != end(c); ++it) {
if(it != begin(c)) out << ",";
dbg_write(out, *it);
}
out << "]";
}
};
template<class T, class C>
struct Dbg<stack<T,C>> {
static void dbg(ostream& out, stack<T,C> stk) {
out << "[";
while(!stk.empty()) {
dbg_write(out,stk.top()); stk.pop();
if(!stk.empty()) out << ",";
}
out << "]";
}
};
template<class T, class C>
struct Dbg<queue<T,C>> {
static void dbg(ostream& out, queue<T,C> que) {
out << "[";
while(!que.empty()) {
dbg_write(out,que.front()); que.pop();
if(!que.empty()) out << ",";
}
out << "]";
}
};
template<class T, class C, class Comp>
struct Dbg<priority_queue<T,C,Comp>> {
static void dbg(ostream& out, priority_queue<T,C,Comp> que) {
out << "[";
while(!que.empty()) {
dbg_write(out,que.top()); que.pop();
if(!que.empty()) out << ",";
}
out << "]";
}
};
template<class T>
void DBG_IMPL(Int line, const char* expr, const T& value) {
cerr << "[L " << line << "]: ";
cerr << expr << " = ";
dbg_write(cerr, value);
cerr << "\n";
}
void DBG_IMPL_HELPER() {}
template<class T, class... TS>
void DBG_IMPL_HELPER(const T& x, const TS&... args) {
dbg_write(cerr, x);
if(sizeof...(args) > 0) {
cerr << ",";
DBG_IMPL_HELPER(args...);
}
}
template<class... TS>
void DBG_IMPL(Int line, const char* expr, const TS&... value) {
cerr << "[L " << line << "]: ";
cerr << "(" << expr << ") = (";
DBG_IMPL_HELPER(value...);
cerr << ")\n";
}
template<size_t N, class T, SFINAE(rank<T>::value == 0)>
void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<Int,N>&, const array<Int,N>&) {
dbg_write(out, x);
}
template<size_t N, class T, SFINAE(rank<T>::value > 0)>
void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<Int,N>& sizes, const array<Int,N>& offs) {
Int k = N - rank<T>::value;
Int off = offs[k];
Int siz = sizes[k];
if(siz == 0) siz = extent<T>::value - off;
out << "[";
FOR(i, off, off+siz) {
if(i != off) out << ",";
DBG_DP_IMPL_HELPER(out, x[i], sizes, offs);
}
out << "]";
}
template<class T, SFINAE(rank<T>::value > 0)>
void DBG_DP_IMPL(Int line, const char* expr, const T& dp,
const array<Int,rank<T>::value>& sizes={},
const array<Int,rank<T>::value>& offs={})
{
cerr << "[L " << line << "]: ";
cerr << expr << " = ";
DBG_DP_IMPL_HELPER<rank<T>::value>(cerr, dp, sizes, offs);
cerr << "\n";
}
template<class T>
void DBG_GRID_IMPL(Int line, const char* expr, const vector<T>& grid) {
cerr << "[L " << line << "]: ";
cerr << expr << ":\n";
for(const auto& row : grid) {
dbg_write(cerr, row);
cerr << "\n";
}
cerr << "\n";
}
#ifdef PROCON_LOCAL
#define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args)
#define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args)
#define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args)
#else
#define DBG(args...)
#define DBG_DP(args...)
#define DBG_GRID(args...)
#endif
// }}}
// modint {{{
template<class Mod>
class ModIntT {
private:
Int v_; // [0,Mod::value)
static Int mod() { return Mod::value; }
static Int normalize(Int x) {
Int res = x % mod();
if(res < 0) res += mod();
return res;
}
public:
ModIntT() : v_(0) {}
ModIntT(Int v) : v_(normalize(v)) {}
explicit operator Int() const { return v_; }
ModIntT operator-() const { return ModIntT(-v_); }
ModIntT& operator+=(ModIntT rhs) {
v_ = normalize(v_ + rhs.v_);
return *this;
}
ModIntT& operator-=(ModIntT rhs) {
v_ = normalize(v_ - rhs.v_);
return *this;
}
ModIntT& operator*=(ModIntT rhs) {
v_ = normalize(v_ * rhs.v_);
return *this;
}
ModIntT& operator++() { return *this += 1; }
ModIntT& operator--() { return *this -= 1; }
ModIntT operator++(int) { return exchange(*this, *this+1); }
ModIntT operator--(int) { return exchange(*this, *this-1); }
ModIntT pow(Int e) const {
return fastpow(*this, e, ModIntT(1));
}
ModIntT inv() const {
Int g,x; tie(g,x,ignore) = EXTGCD(v_, mod());
ASSERT(g == 1);
return ModIntT(x);
}
friend ModIntT operator+(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) += rhs; }
friend ModIntT operator+(ModIntT lhs, Int rhs) { return ModIntT(lhs) += rhs; }
friend ModIntT operator+(Int lhs, ModIntT rhs) { return ModIntT(rhs) += lhs; }
friend ModIntT operator-(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) -= rhs; }
friend ModIntT operator-(ModIntT lhs, Int rhs) { return ModIntT(lhs) -= rhs; }
friend ModIntT operator-(Int lhs, ModIntT rhs) { return ModIntT(rhs) -= lhs; }
friend ModIntT operator*(ModIntT lhs, ModIntT rhs) { return ModIntT(lhs) *= rhs; }
friend ModIntT operator*(ModIntT lhs, Int rhs) { return ModIntT(lhs) *= rhs; }
friend ModIntT operator*(Int lhs, ModIntT rhs) { return ModIntT(rhs) *= lhs; }
friend bool operator==(ModIntT lhs, ModIntT rhs) { return Int(lhs) == Int(rhs); }
friend bool operator==(ModIntT lhs, Int rhs) { return lhs == ModIntT(rhs); }
friend bool operator==(Int lhs, ModIntT rhs) { return ModIntT(lhs) == rhs; }
friend bool operator!=(ModIntT lhs, ModIntT rhs) { return !(lhs == rhs); }
friend bool operator!=(ModIntT lhs, Int rhs) { return !(lhs == rhs); }
friend bool operator!=(Int lhs, ModIntT rhs) { return !(lhs == rhs); }
};
template<class Mod>
struct ProconHash<ModIntT<Mod>> {
size_t operator()(ModIntT<Mod> x) const noexcept {
return procon_hash_value(Int(x));
}
};
template<class Mod>
struct Scan<ModIntT<Mod>> {
using R = ModIntT<Mod>;
static R scan(istream& in) {
Int v = Scan<Int>::scan(in);
return ModIntT<Mod>(v);
}
};
template<class Mod>
struct Fmt<ModIntT<Mod>> {
static void fmt(ostream& out, ModIntT<Mod> x) {
fmt_write(out, Int(x));
}
};
template<class Mod>
struct Dbg<ModIntT<Mod>> {
static void dbg(ostream& out, ModIntT<Mod> x) {
dbg_write(out, Int(x));
}
};
template<Int M>
using ModIntC = ModIntT<integral_constant<Int,M>>;
using ModInt = ModIntC<MOD>;
// }}}
// rng {{{
// http://prng.di.unimi.it/xoroshiro128plus.c
struct ProconUrbg {
using result_type = u64;
static constexpr result_type min() { return numeric_limits<result_type>::min(); }
static constexpr result_type max() { return numeric_limits<result_type>::max(); }
ProconUrbg(u64 s0, u64 s1) : state_{s0,s1} {}
result_type operator()() {
u64 s0 = state_[0];
u64 s1 = state_[1];
u64 res = s0 + s1;
s1 ^= s0;
state_[0] = ((s0<<24)|(s0>>40)) ^ s1 ^ (s1<<16);
state_[1] = (s1<<37)|(s1>>27);
return res;
}
private:
u64 state_[2];
};
ProconUrbg& PROCON_URBG() {
static u64 s0 = u64(chrono::system_clock::now().time_since_epoch().count());
static u64 s1 = u64(&s0);
static ProconUrbg urbg(s0, s1);
return urbg;
}
// }}}
// init {{{
struct ProconInit {
ProconInit() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin.exceptions(ios::failbit | ios::badbit);
cout << fixed << setprecision(COUT_PREC);
#ifdef PROCON_LOCAL
cerr << fixed << setprecision(2);
#endif
if(COUT_AUTOFLUSH)
cout << unitbuf;
}
} PROCON_INIT;
// }}}
// }}}
// graph {{{
auto udgraph_list(Int n, const vector<pair<Int,Int>>& es) {
vector<vector<Int>> g(n);
for(const auto& e : es) {
Int a,b; tie(a,b) = e;
g[a].emplace_back(b);
g[b].emplace_back(a);
}
return g;
}
auto digraph_list(Int n, const vector<pair<Int,Int>>& es) {
vector<vector<Int>> g(n);
for(const auto& e : es) {
Int a,b; tie(a,b) = e;
g[a].emplace_back(b);
}
return g;
}
auto udgraph_matrix(Int n, const vector<pair<Int,Int>>& es) {
vector<vector<Int>> g(n, vector<Int>(n,INF));
REP(i, n) { g[i][i] = 0; }
for(const auto& e : es) {
Int a,b; tie(a,b) = e;
g[a][b] = g[b][a] = 1;
}
return g;
}
auto digraph_matrix(Int n, const vector<pair<Int,Int>>& es) {
vector<vector<Int>> g(n, vector<Int>(n,INF));
REP(i, n) { g[i][i] = 0; }
for(const auto& e : es) {
Int a,b; tie(a,b) = e;
g[a][b] = 1;
}
return g;
}
template<class T>
auto wudgraph_list(Int n, const vector<tuple<Int,Int,T>>& es) {
vector<vector<pair<Int,T>>> g(n);
for(const auto& e : es) {
Int a,b; T c; tie(a,b,c) = e;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
return g;
}
template<class T>
auto wdigraph_list(Int n, const vector<tuple<Int,Int,T>>& es) {
vector<vector<pair<Int,T>>> g(n);
for(const auto& e : es) {
Int a,b; T c; tie(a,b,c) = e;
g[a].emplace_back(b, c);
}
return g;
}
template<class T>
auto wudgraph_matrix(Int n, const vector<tuple<Int,Int,T>>& es) {
vector<vector<T>> g(n, vector<T>(n,PROCON_INF<T>()));;
REP(i, n) { g[i][i] = T{}; }
for(const auto& e : es) {
Int a,b; T c; tie(a,b,c) = e;
g[a][b] = g[b][a] = c;
}
return g;
}
template<class T>
auto wdigraph_matrix(Int n, const vector<tuple<Int,Int,T>>& es) {
vector<vector<T>> g(n, vector<T>(n,PROCON_INF<T>()));;
REP(i, n) { g[i][i] = T{}; }
for(const auto& e : es) {
Int a,b; T c; tie(a,b,c) = e;
g[a][b] = c;
}
return g;
}
// 単純無向グラフが木かどうか判定する
//
// g: 隣接リスト表現(頂点数 n > 0)
bool graph_is_tree(const vector<vector<Int>>& g) {
Int n = SIZE(g);
ASSERT(n > 0);
Int edge_cnt = 0;
vector<bool> visited(n, false);
auto dfs = FIX([&g,&edge_cnt,&visited](auto&& self, Int v) -> void {
visited[v] = true;
for(Int to : g[v]) {
if(visited[to]) continue;
++edge_cnt;
self(to);
}
});
dfs(0);
bool connected = ALL(all_of, visited, [](bool b) { return b; });
return edge_cnt == n-1 && connected;
}
// BFSで重みなしグラフ上の単一始点最短経路を求める
//
// (ds,ps) を返す
// ds[i]: start から点 i への最短距離(到達不能な点は INF)
// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)
tuple<vector<Int>,vector<Int>> graph_bfs(const vector<vector<Int>>& g, Int start) {
Int n = SIZE(g);
vector<Int> ds(n, INF);
vector<Int> ps(n, -1);
queue<Int> que;
que.emplace(start);
ds[start] = 0;
while(!que.empty()) {
Int v = POP(que);
for(Int to : g[v]) {
if(ds[to] != INF) continue;
que.emplace(to);
ds[to] = ds[v] + 1;
ps[to] = v;
}
}
return make_tuple(ds, ps);
}
// ダイクストラ法
//
// (ds,ps) を返す
// ds[i]: start から点 i への最短距離(到達不能な点は PROCON_INF<T>())
// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)
template<typename T>
tuple<vector<T>,vector<Int>> graph_dijkstra(const vector<vector<pair<Int,T>>>& g, Int start) {
Int n = SIZE(g);
vector<T> ds(n, PROCON_INF<T>());
vector<Int> ps(n, -1);
auto que = priority_queue_make<pair<T,Int>>(greater<>{});
ds[start] = T{};
que.emplace(T{}, start);
Int n_remain = n;
while(!que.empty()) {
T d; Int v; tie(d,v) = POP(que);
if(ds[v] < d) continue;
if(--n_remain == 0) break;
for(const auto& p : g[v]) {
Int to; T cost; tie(to,cost) = p;
T d_new = d + cost;
if(chmin(ds[to], d_new)) {
ps[to] = v;
que.emplace(d_new, to);
}
}
}
return make_tuple(ds, ps);
}
// 辺のコストが小さい非負整数の場合の最良優先探索(01-BFS の一般化)
// 全ての辺のコストは [0,k] であること
//
// (ds,ps) を返す
// ds[i]: start から点 i への最短距離(到達不能な点は INF)
// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)
tuple<vector<Int>,vector<Int>> graph_k_bfs(const vector<vector<pair<Int,Int>>>& g, Int k, Int start) {
Int n = SIZE(g);
vector<Int> ds(n, INF);
vector<Int> ps(n, -1);
vector<queue<Int>> ques(k+1);
auto enqueue = [&ques](Int to, Int cost) {
ques[cost].emplace(to);
};
auto dequeue = [&ques]() -> Int {
for(auto& que : ques)
if(!que.empty())
return POP(que);
return -1;
};
enqueue(start, 0);
ds[start] = 0;
Int v;
while((v = dequeue()) != -1) {
for(const auto& p : g[v]) {
Int to,cost; tie(to,cost) = p;
Int d_new = ds[v] + cost;
if(chmin(ds[to], d_new)) {
ps[to] = v;
enqueue(to, cost);
}
}
}
return make_tuple(ds, ps);
}
// ベルマンフォード法
//
// 負閉路が存在する場合、最短距離が負の無限大になる点が生じる。
// そのような点を全て検出するため、2*n 回ループしている
// (一般的な実装の倍の回数。ただし更新がなくなったら打ち切る)
//
// (ds,ps) を返す
// ds[i]: start から点 i への最短距離(到達不能なら INF, 負の無限大なら -INF)
// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)
template<typename T>
tuple<vector<T>,vector<Int>> graph_bellman(const vector<vector<pair<Int,T>>>& g, Int start) {
Int n = SIZE(g);
vector<T> ds(n, PROCON_INF<T>());
vector<Int> ps(n, -1);
ds[start] = T{};
REP(i, 2*n) {
bool update = false;
REP(from, n) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
if(ds[from] == PROCON_INF<T>()) continue;
for(const auto& p : g[from]) {
Int to; T cost; tie(to,cost) = p;
T d_new = ds[from]==-PROCON_INF<T>() ? -PROCON_INF<T>() : ds[from]+cost;
if(d_new < ds[to]) {
update = true;
ds[to] = i >= n-1 ? -PROCON_INF<T>() : d_new;
ps[to] = from;
}
}
#pragma GCC diagnostic pop
}
if(!update) break;
}
return make_tuple(ds, ps);
}
// SPFA (Shortest Path Faster Algorithm)
//
// 理論上はベルマンフォードより速いはずだが、実際はそうでもなさげ
// 最短距離が負の無限大になる点を全て検出するため 2*n 回ループしている
// (一般的な実装の倍の回数。ただし更新がなくなったら打ち切る)
//
// (ds,ps) を返す
// ds[i]: start から点 i への最短距離(到達不能なら INF, 負の無限大なら -INF)
// ps[i]: 最短経路木における点 i の親(start および到達不能な点は -1)
template<typename T>
tuple<vector<T>,vector<Int>> graph_spfa(const vector<vector<pair<Int,T>>>& g, Int start) {
Int n = SIZE(g);
vector<T> ds(n, PROCON_INF<T>());
vector<Int> ps(n, -1);
queue<Int> que;
vector<bool> in_que(n, false);
const auto enqueue = [&que,&in_que](Int v) { que.emplace(v); in_que[v] = true; };
const auto dequeue = [&que,&in_que]() { Int v = POP(que); in_que[v] = false; return v; };
ds[start] = T{};
enqueue(start);
REP(i, 2*n) {
REP(_, que.size()) {
Int from = dequeue();
for(const auto& p : g[from]) {
Int to; T cost; tie(to,cost) = p;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
T d_new = ds[from]==-PROCON_INF<T>() ? -PROCON_INF<T>() : ds[from]+cost;
if(d_new < ds[to]) {
ds[to] = i >= n-1 ? -PROCON_INF<T>() : d_new;
ps[to] = from;
if(!in_que[to]) enqueue(to);
}
#pragma GCC diagnostic pop
}
}
if(que.empty()) break;
}
return make_tuple(ds, ps);
}
// ワーシャルフロイド法
//
// g は隣接行列 (g[from][to]) で、from == to の場合 0, from != to で辺
// がない場合 INF
//
// g は全点対間最短距離で上書きされる
// (ok,nex) を返す
// ok: 負閉路が存在しない場合に限り true
// nex[i][j]: i から j へ最短経路で行くとき、次に辿るべき点(到達不能なら -1)
template<typename T>
tuple<bool,vector<vector<Int>>> graph_floyd(vector<vector<T>>& g) {
Int n = SIZE(g);
vector<vector<Int>> nex(n, vector<Int>(n,-1));
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
REP(i, n) REP(j, n) {
if(g[i][j] != PROCON_INF<T>())
nex[i][j] = j;
}
REP(k, n) {
REP(i, n) {
if(g[i][k] == PROCON_INF<T>()) continue;
REP(j, n) {
if(g[k][j] == PROCON_INF<T>()) continue;
if(chmin(g[i][j], g[i][k] + g[k][j])) {
nex[i][j] = nex[i][k];
}
if(i == j && g[i][j] < 0) return make_tuple(false, nex);
}
}
}
#pragma GCC diagnostic pop
return make_tuple(true, nex);
}
// TODO: 重みあり/なし両対応
// トポロジカルソート
// queue を MinHeap に変えると辞書順最小のものが求まる
//
// (ok,res) を返す
// ok: DAGであったかどうか
// res: 結果
tuple<bool,vector<Int>> graph_tsort(const vector<vector<Int>>& g) {
Int n = SIZE(g);
vector<Int> res;
res.reserve(n);
vector<Int> deg_in(n, 0);
for(const auto& tos : g)
for(auto to : tos)
++deg_in[to];
queue<Int> que;
REP(v, n) {
if(deg_in[v] == 0)
que.emplace(v);
}
while(!que.empty()) {
Int v = POP(que);
res.emplace_back(v);
for(auto to : g[v]) {
if(--deg_in[to] > 0) continue;
que.emplace(to);
}
}
bool ok = SIZE(res) == n;
return make_tuple(ok, res);
}
// TODO: 重みあり/なし両対応
// (関節点リスト,橋リスト) を返す
tuple<vector<Int>,vector<pair<Int,Int>>> graph_lowlink(const vector<vector<Int>>& g) {
Int n = SIZE(g);
vector<Int> ord(n, -1);
vector<Int> low(n, -1);
vector<Int> articulations;
vector<pair<Int,Int>> bridges;
auto dfs = FIX([&g,&ord,&low,&articulations,&bridges](auto&& self, Int v, Int parent, Int k) -> void {
low[v] = ord[v] = k;
bool arti = false;
Int n_child = 0;
for(Int to : g[v]) {
// 親または後退辺
if(ord[to] != -1) {
if(to != parent)
chmin(low[v], ord[to]);
continue;
}
// 子を辿り、low[v] を更新
++n_child;
self(to, v, k+1);
chmin(low[v], low[to]);
// 関節点判定(根でない場合)
if(parent != -1 && low[to] >= ord[v])
arti = true;
// 橋判定
if(low[to] > ord[v])
bridges.emplace_back(minmax(v,to));
}
// 関節点判定(根の場合)
if(parent == -1 && n_child > 1)
arti = true;
if(arti)
articulations.emplace_back(v);
});
dfs(0, -1, 0);
return make_tuple(articulations, bridges);
}
// 各頂点の (indegree,outdegree) のリストを返す (隣接リスト版)
vector<pair<Int,Int>> graph_degrees_list(const vector<vector<Int>>& g) {
Int n = SIZE(g);
vector<pair<Int,Int>> res(n, {0,0});
REP(from, n) {
for(Int to : g[from]) {
++res[from].second;
++res[to].first;
}
}
return res;
}
// 各頂点の (indegree,outdegree) のリストを返す (隣接行列版)
vector<pair<Int,Int>> graph_degrees_matrix(const vector<vector<Int>>& g) {
Int n = SIZE(g);
vector<pair<Int,Int>> res(n, {0,0});
REP(from, n) REP(to, n) {
Int k = g[from][to];
res[from].second += k;
res[to].first += k;
}
return res;
}
// グラフのオイラー路 (隣接リスト版)
//
// g は破壊される
// start: 始点
// digraph: 有向グラフか?
vector<Int> graph_euler_trail_list(vector<vector<Int>>& g, Int start, bool digraph) {
// スタックオーバーフロー回避のため再帰を使わず自前の stack で処理
enum Action { CALL, RESUME };
vector<Int> res;
stack<tuple<Action,Int>> stk;
stk.emplace(CALL, start);
while(!stk.empty()) {
Action act; Int v; tie(act,v) = POP(stk);
switch(act) {
case CALL:
stk.emplace(RESUME, v);
while(!g[v].empty()) {
Int to = g[v].back(); g[v].pop_back();
if(!digraph)
g[to].erase(ALL(find, g[to], v));
stk.emplace(CALL, to);
}
break;
case RESUME:
res.emplace_back(v);
break;
default: ASSERT(false);
}
}
ALL(reverse, res);
return res;
}
// 無向グラフのオイラー路 (隣接行列版)
//
// g[v][w]: v,w 間の辺の本数 (破壊される)
// start: 始点
// digraph: 有向グラフか?
vector<Int> graph_euler_trail_matrix(vector<vector<Int>>& g, Int start, bool digraph) {
// スタックオーバーフロー回避のため再帰を使わず自前の stack で処理
enum Action { CALL, RESUME };
Int n = SIZE(g);
vector<Int> res;
stack<tuple<Action,Int>> stk;
stk.emplace(CALL, start);
while(!stk.empty()) {
Action act; Int v; tie(act,v) = POP(stk);
switch(act) {
case CALL:
stk.emplace(RESUME, v);
REP(to, n) {
if(g[v][to] == 0) continue;
--g[v][to];
if(!digraph)
--g[to][v];
stk.emplace(CALL, to);
}
break;
case RESUME:
res.emplace_back(v);
break;
default: ASSERT(false);
}
}
ALL(reverse, res);
return res;
}
// }}}
//--------------------------------------------------------------------
[[noreturn]] void impossible() {
PRINTLN("-1");
EXIT();
}
void solve() {
Int N = RD();
auto E = RD_VEC<pair<Int1,Int1>>(N-1);
auto G = udgraph_list(N, E);
auto dp = vec_make<Int>(N,2, 0);
auto dfs = FIX([&](auto&& self, Int v, Int p) -> void {
dp[v][0] = 1;
dp[v][1] = 0;
for(Int to : G[v]) {
if(to == p) continue;
self(to, v);
dp[v][0] += MAX(dp[to][0]-1, dp[to][1]);
dp[v][1] += MAX(dp[to][0], dp[to][1]);
}
});
dfs(0, -1);
DBG(dp);
auto ans = MAX(dp[0][0], dp[0][1]);
PRINTLN(ans);
}
signed main() {
Int T = 1; //RD();
LOOP(T) {
solve();
}
EXIT();
}