//////////////////////////////////////////////////////////////////////////////// // Give me AC!!! // //////////////////////////////////////////////////////////////////////////////// #include #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; using ll = long long; using ld = long double; using graph = vector>; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define REPD(i,n) for(ll i=n-1;i>=0;i--) #define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) #define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--) //xにはvectorなどのコンテナ #define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい #define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく #define MAX(x) *max_element(ALL(x)) //最大値を求める #define MIN(x) *min_element(ALL(x)) //最小値を求める #define PQ priority_queue,vector>,greater>> #define PB push_back //vectorヘの挿入 #define MP make_pair //pairのコンストラクタ #define S second //pairの二つ目の要素 #define coutY cout<<"YES"< a(b) #define vl(a,b) vector a(b) #define vs(a,b) vector a(b) #define vll(a,b,c) vector> a(b, vector(c)); #define intque(a) queue a; #define llque(a) queue a; #define intque2(a) priority_queue, greater> a; #define llque2(a) priority_queue, greater> a; #define pushback(a,b) a.push_back(b) #define mapii(M1) map M1; #define cou(v,x) count(v.begin(), v.end(), x) #define mapll(M1) map M1; #define mapls(M1) map M1; #define mapsl(M1) map M1; #define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a #define sor(a) sort(a.begin(), a.end()) #define rever(a) reverse(a.begin(),a.end()) #define rep(i,a) for(ll i=0;i>n[i] #define vcout(n) for(ll i=0;i>n[i][j] //const ll mod = 998244353; //const ll MOD = 998244353; const ll MOD = 1000000007; const ll mod = 1000000007; constexpr ll MAX = 5000000; //const ll _max = 9223372036854775807; const ll _max = 1223372036854775807; const ll INF = 2000000000000000000; static const long double pi = 3.141592653589793; const int MAX_COL=350; const int MAX_ROW=350; ll fac[MAX],finv[MAX],inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int modPow(long long a, long long n, long long p) { if (a == 0 && n == 0) return 0; if (n == 0) return 1; // 0乗にも対応する場合 if (n == 1) return a % p; if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p; long long t = modPow(a, n / 2, p); return (t * t) % p; } ll clocks(ll a,ll b,ll c){ return a*3600+b*60+c; } ll divup(ll b,ll d){ if(b%d==0){ return b/d; } else{ return b/d+1; } } struct edge { int to; // 辺の行き先 int weight; // 辺の重み edge(int t, int w) : to(t), weight(w) { } }; using Graphw = vector>; ll zero(ll a){ return max(ll(0),a); } template< typename T > struct FormalPowerSeries : vector< T > { using vector< T >::vector; using P = FormalPowerSeries; using MULT = function< P(P, P) >; static MULT &get_mult() { static MULT mult = nullptr; return mult; } static void set_fft(MULT f) { get_mult() = f; } void shrink() { while(this->size() && this->back() == T(0)) this->pop_back(); } P operator+(const P &r) const { return P(*this) += r; } P operator+(const T &v) const { return P(*this) += v; } P operator-(const P &r) const { return P(*this) -= r; } P operator-(const T &v) const { return P(*this) -= v; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(const T &v) const { return P(*this) *= v; } P operator/(const P &r) const { return P(*this) /= r; } P operator%(const P &r) const { return P(*this) %= r; } P &operator+=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] += r[i]; return *this; } P &operator+=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] += r; return *this; } P &operator-=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i]; shrink(); return *this; } P &operator-=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] -= r; shrink(); return *this; } P &operator*=(const T &v) { const int n = (int) this->size(); for(int k = 0; k < n; k++) (*this)[k] *= v; return *this; } P &operator*=(const P &r) { if(this->empty() || r.empty()) { this->clear(); return *this; } assert(get_mult() != nullptr); return *this = get_mult()(*this, r); } P &operator%=(const P &r) { return *this -= *this / r * r; } P operator-() const { P ret(this->size()); for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i]; return ret; } P &operator/=(const P &r) { if(this->size() < r.size()) { this->clear(); return *this; } int n = this->size() - r.size() + 1; return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n); } P pre(int sz) const { return P(begin(*this), begin(*this) + min((int) this->size(), sz)); } P operator>>(int sz) const { if(this->size() <= sz) return {}; P ret(*this); ret.erase(ret.begin(), ret.begin() + sz); return ret; } P operator<<(int sz) const { P ret(*this); ret.insert(ret.begin(), sz, T(0)); return ret; } P rev(int deg = -1) const { P ret(*this); if(deg != -1) ret.resize(deg, T(0)); reverse(begin(ret), end(ret)); return ret; } P diff() const { const int n = (int) this->size(); P ret(max(0, n - 1)); for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i); return ret; } P integral() const { const int n = (int) this->size(); P ret(n + 1); ret[0] = T(0); for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1); return ret; } // F(0) must not be 0 P inv(int deg = -1) const { assert(((*this)[0]) != T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1) / (*this)[0]}); for(int i = 1; i < deg; i <<= 1) { ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1); } return ret.pre(deg); } // F(0) must be 1 P log(int deg = -1) const { assert((*this)[0] == 1); const int n = (int) this->size(); if(deg == -1) deg = n; return (this->diff() * this->inv(deg)).pre(deg - 1).integral(); } P sqrt(int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; if((*this)[0] == T(0)) { for(int i = 1; i < n; i++) { if((*this)[i] != T(0)) { if(i & 1) return {}; if(deg - i / 2 <= 0) break; auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2); if(ret.size() < deg) ret.resize(deg, T(0)); return ret; } } return P(deg, 0); } P ret({T(1)}); T inv2 = T(1) / T(2); for(int i = 1; i < deg; i <<= 1) { ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2; } return ret.pre(deg); } // F(0) must be 0 P exp(int deg = -1) const { assert((*this)[0] == T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1)}); for(int i = 1; i < deg; i <<= 1) { ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1); } return ret.pre(deg); } P pow(int64_t k, int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; for(int i = 0; i < n; i++) { if((*this)[i] != T(0)) { T rev = T(1) / (*this)[i]; P C(*this * rev); P D(n - i); for(int j = i; j < n; j++) D[j - i] = C[j]; D = (D.log() * k).exp() * (*this)[i].pow(k); P E(deg); if(i * k > deg) return E; auto S = i * k; for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j]; return E; } } return *this; } T eval(T x) const { T r = 0, w = 1; for(auto &v : *this) { r += w * v; w *= x; } return r; } }; //aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数 ll expless(ll a,ll b){ ll k=0; ll o=1; while(a>=o){ k++; o=o*b; } return k; } //aをb進法で表す //b進法のaを10進法に直す ll tenbase(ll a,ll b){ ll c=expless(a,10); ll ans=0; ll k=1; for(int i=0;i > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } //aがbで何回割り切るか ll exp(ll a,ll b){ ll ans=0; while(a%b==0){ a=a/b; ans++; } return ans; } const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; const int X[6]={1,1,0,-1,-1,0}; const int Y[6]={0,1,1,0,-1,-1}; template vector smallest_prime_factors(T n) { vector spf(n + 1); for (int i = 0; i <= n; i++) spf[i] = i; for (T i = 2; i * i <= n; i++) { // 素数だったら if (spf[i] == i) { for (T j = i * i; j <= n; j += i) { // iを持つ整数かつまだ素数が決まっていないなら if (spf[j] == j) { spf[j] = i; } } } } return spf; } vector> factolization(ll x, vector &spf) { vector> ret; ll p; ll z; while (x != 1) { p=(spf[x]); z=0; while(x%p==0){ z++; x /= p; } ret.push_back({p, z}); } return ret; } vector is; vector prime_(ll n){ is.resize(n+1, true); is[0] = false; is[1] = false; vector primes; for (int i=2; i<=n; i++) { if (is[i] == true){ primes.push_back(i); for (int j=i*2; j<=n; j+=i){ is[j] = false; } } } return primes; } vector dijkstra(ll f,ll n,vector>>& edge){ //最短経路としてどの頂点が確定済みかをチェックする配列 vector confirm(n,false); //それぞれの頂点への最短距離を保存する配列 //始点は0,始点以外はINFで最短距離を初期化する vector mincost(n,INF);mincost[f]=0; //確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queue PQ mincand;mincand.push({mincost[f],f}); //mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す while(!mincand.empty()){ //最短距離でたどり着くと思われる頂点を取り出す vector next=mincand.top();mincand.pop(); //すでにその頂点への最短距離が確定済みの場合は飛ばす if(confirm[next[1]]) continue; //確定済みではない場合は確定済みにする confirm[next[1]]=true; //その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数 vector>& v=edge[next[1]];ll l=SIZE(v); REP(i,l){ //辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない) if(confirm[v[i][0]]) continue; //(✳︎1) //辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす) if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2) //更新 mincost[v[i][0]]=next[0]+v[i][1]; //更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入 mincand.push({mincost[v[i][0]],v[i][0]}); } } return mincost; } ll so(ll a){ ll ans=0; if(a==0){ return 0; } while(a%2==0){ a/=2; ans++; } return ans; } ll HOM(ll n,ll r){ return COM(n+r-1,r); } ll binary(ll bina){ ll ans = 0; for (ll i = 0; bina>0 ; i++) { ans = ans+(bina%2)*pow(10,i); bina = bina/2; } return ans; } vector enum_divisors(long long N) { vector res; for (long long i = 1; i * i <= N; ++i) { if (N % i == 0) { res.push_back(i); // 重複しないならば i の相方である N/i も push if (N/i != i) res.push_back(N/i); } } // 小さい順に並び替える sort(res.begin(), res.end()); return res; } vector zaatu(vector a,ll n){ map mp; for (int i = 0; i < n; i++) { cin >> a[i]; mp[a[i]] = 0; } // 小さい値から順に番号を付けていく ll num = 0; for (auto x : mp) { mp[x.first] = num; num++; } vector ans; for(int i=0;i t,ll key){ auto iter = lower_bound(ALL(t), key); auto iter2 = upper_bound(ALL(t), key); if((iter-t.begin())!=(iter2-t.begin())){ return 1; } else{ return 0; } } template struct SegmentTree { using T = typename Monoid::value_type; std::vector tree; SegmentTree() = default; explicit SegmentTree(ll n) :tree(n << 1, Monoid::identity()) {}; template SegmentTree(InputIterator first, InputIterator last) { tree.assign(distance(first, last) << 1, Monoid::identity()); ll i; i = size(); for (InputIterator itr = first; itr != last; itr++) { tree[i++] = *itr; } for (i = size() - 1; i > 0; i--) { tree[i] = Monoid::operation(tree[(i << 1)], tree[(i << 1) | 1]); } }; inline ll size() { return tree.size() >> 1; }; inline T operator[] (ll k) { return tree[k + size()]; }; void add(ll k, const T dat) { k += size(); tree[k] += dat; while(k > 1) { k >>= 1; tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]); } }; void update(ll k, const T dat) { k += size(); tree[k] = dat; while(k > 1) { k >>= 1; tree[k] = Monoid::operation(tree[(k << 1)], tree[(k << 1) | 1]); } }; T fold(ll l, ll r) { l += size(); //points leaf r += size(); T lv = Monoid::identity(); T rv = Monoid::identity(); while (l < r) { if (l & 1) lv = Monoid::operation(lv, tree[l++]); if (r & 1) rv = Monoid::operation(tree[--r], rv); l >>= 1; r >>= 1; } return Monoid::operation(lv, rv); }; template inline ll sub_tree_search(ll i, T sum, F f) { while (i < size()) { T x = Monoid::operation(sum, tree[i << 1]); if (f(x)) { i = i << 1; } else { sum = x; i = (i << 1) | 1; } } return i - size(); } template ll search(ll l, F f) { l += size(); ll r = size() * 2; //r = n; ll tmpr = r; ll shift = 0; T sum = Monoid::identity(); while (l < r) { if (l & 1) { if (f(Monoid::operation(sum, tree[l]))) { return sub_tree_search(l, sum, f); } sum = Monoid::operation(sum, tree[l]); l++; } l >>= 1; r >>= 1; shift++; } while (shift > 0) { shift--; r = tmpr >> shift; if (r & 1) { r--; if (f(Monoid::operation(sum, tree[r]))) { return sub_tree_search(r, sum, f); } sum = Monoid::operation(sum, tree[r]); } } return -1; }; }; using namespace std; using llong = long long; struct Monoid { using value_type = ll; inline static ll identity() { return 0; }; inline static ll operation(ll a, ll b) { return a+b; }; }; class mint { long long x; public: mint(long long x=0) : x((x%mod+mod)%mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; int ctoi(const char c){ switch(c){ case '0': return 0; case '1': return 1; case '2': return 2; case '3': return 3; case '4': return 4; case '5': return 5; case '6': return 6; case '7': return 7; case '8': return 8; case '9': return 9; default : return -1; } } ll ord(ll a,ll b){ ll ans=0; while(a%b==0){ ans++; a/=b; } return ans; } ll atll(ll a,ll b){ b++; ll c=expless(a,10); ll d=c-b; ll f=1; for(int i=0;i par; // 各元の親を表す配列 vector siz; // 素集合のサイズを表す配列(1 で初期化) // Constructor UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } // Member Function // Find ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } // Union(Unite, Merge) bool merge(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool issame(ll x, ll y) { // 連結判定 return root(x) == root(y); } ll size(ll x) { // 素集合のサイズ return siz[root(x)]; } }; struct BitMatrix { int H, W; bitset val[MAX_ROW]; BitMatrix(int m = 1, int n = 1) : H(m), W(n) {} inline bitset& operator [] (int i) {return val[i];} }; int GaussJordan(BitMatrix &A, bool is_extended = false) { int rank = 0; for (int col = 0; col < A.W; ++col) { if (is_extended && col == A.W - 1) break; int pivot = -1; for (int row = rank; row < A.H; ++row) { if (A[row][col]) { pivot = row; break; } } if (pivot == -1) continue; swap(A[pivot], A[rank]); for (int row = 0; row < A.H; ++row) { if (row != rank && A[row][col]) A[row] ^= A[rank]; } ++rank; } return rank; } int pos(const char c){ if('a' <= c && c <= 'z') return (c-'a'); return -1; } ll x[4]={1,0,-1,0}; ll y[4]={0,1,0,-1}; int main() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(30); ll a; cin>>a; vector n(a-1); vcin(n); ll sum=0; for(int i=0;i