結果

問題 No.1637 Easy Tree Query
ユーザー ymduuymduu
提出日時 2021-08-06 21:31:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 62,308 bytes
コンパイル時間 7,275 ms
コンパイル使用メモリ 439,844 KB
最終ジャッジ日時 2024-11-15 05:16:04
合計ジャッジ時間 9,664 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:40:41: error: redefinition of 'T boost::qvm::sqrt(T) [with T = long double]'
   40 |                 template <> long double sqrt<long double>(long double a)
      |                                         ^~~~~~~~~~~~~~~~~
In file included from /boost_git/boost/qvm/mat_operations.hpp:14,
                 from main.cpp:15:
/boost_git/boost/qvm/math.hpp:96:50: note: 'T boost::qvm::sqrt(T) [with T = long double]' previously declared here
   96 | template <> BOOST_QVM_INLINE_TRIVIAL long double sqrt<long double>( long double x ) { return ::sqrtl(x); }
      |                                                  ^~~~~~~~~~~~~~~~~
main.cpp:44:41: error: redefinition of 'T boost::qvm::sin(T) [with T = long double]'
   44 |                 template <> long double sin<long double>(long double a)
      |                                         ^~~~~~~~~~~~~~~~
/boost_git/boost/qvm/math.hpp:86:50: note: 'T boost::qvm::sin(T) [with T = long double]' previously declared here
   86 | template <> BOOST_QVM_INLINE_TRIVIAL long double sin<long double>( long double x ) { return ::sinl(x); }
      |                                                  ^~~~~~~~~~~~~~~~
main.cpp:48:41: error: redefinition of 'T boost::qvm::cos(T) [with T = long double]'
   48 |                 template <> long double cos<long double>(long double a)
      |                                         ^~~~~~~~~~~~~~~~
/boost_git/boost/qvm/math.hpp:85:50: note: 'T boost::qvm::cos(T) [with T = long double]' previously declared here
   85 | template <> BOOST_QVM_INLINE_TRIVIAL long double cos<long double>( long double x ) { return ::cosl(x); }
      |                                                  ^~~~~~~~~~~~~~~~
main.cpp: In member function 'std::vector<long long int> StressTest::create_permutation(long long int)':
main.cpp:2223:9: warning: no return statement in function returning non-void [-Wreturn-type]
 2223 |         }
      |         ^
main.cpp: In member function 'Graph StressTest::create_tree(long 

ソースコード

diff #
プレゼンテーションモードにする

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4244) //
// AtCoder ACL
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#define ACL_ENABLED
#endif
#if __has_include(<boost/multiprecision/cpp_int.hpp>)
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/math/constants/constants.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/math/constants/constants.hpp>
#include <boost/qvm/mat.hpp>
#include <boost/qvm/mat_operations.hpp>
#include <boost/qvm/quat.hpp>
#include <boost/qvm/quat_operations.hpp>
#include <boost/qvm/to_string.hpp>
#include <boost/qvm/vec.hpp>
#include <boost/qvm/vec_access.hpp>
#include <boost/qvm/vec_mat_operations.hpp>
#include <boost/qvm/vec_operations.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/irange.hpp>
#define BOOST_ENABLED
using namespace boost::multiprecision;
namespace ublas = boost::numeric::ublas;
namespace qvm = boost::qvm;
using Vector3D = boost::qvm::vec<long double, 3>;
using Quaternion = boost::qvm::quat<long double>;
using Matrix3x3 = boost::qvm::mat<long double, 3, 3>;
using Matrix4x4 = boost::qvm::mat<long double, 4, 4>;
// constexpr long double PI = boost::math::constants::pi<long double>();
#if defined(ACL_ENABLED) && defined(ONLINE_JUDGE) // TORIAEZU: AtCoder ONLINE_JUDGE long double (Boost 1_73
     qvm 使)
namespace boost {
namespace qvm {
template <> long double sqrt<long double>(long double a)
{
return sqrtl(a);
}
template <> long double sin<long double>(long double a)
{
return sinl(a);
}
template <> long double cos<long double>(long double a)
{
return cosl(a);
}
}
}
#endif
#endif
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#include <sstream>
#include <memory>
#define BIT(nr) (1UL << (nr))
#define int long long
//#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807 //
#define LL_HALFMAX 9223372036854775807 / 2 //
#define MIN -(9223372036854775807 / 2)
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair
template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
const double PI = 3.14159265358979323846;
// map k e e.second chmin(e.second, v) v
// ( ) true, ( ) false
template<typename MAP, typename T1, typename T2>
bool insert_or_chmin(MAP& map, T1 k, T2 v) {
if (map.find(k) == map.end()) {
//
map[k] = v;
return true;
}
else {
// chmin
chmin(map[k], v);
return false;
}
}
// chmax
template<typename MAP, typename T1, typename T2>
bool insert_or_chmax(MAP& map, T1 k, T2 v) {
if (map.find(k) == map.end()) {
//
map[k] = v;
return true;
}
else {
// chmax
chmax(map[k], v);
return false;
}
}
using namespace std;
using pint = pair<int, int>;
//
#ifdef DEBUG
template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
o << "{"; for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? ", " : "") << v[i]; o << "}"; return o;
}
#endif // DEBUG
template <class T>ostream &operator<<(ostream &o, const vector<T>&v)
{
for (int i = 0; i<(int)v.size(); i++)o << (i>0 ? " " : "") << v[i]; return o;
}
int dx[4] = { 0, 1, 0, -1 }; // x
int dy[4] = { 1, 0, -1, 0 }; // y
int dxp[4] = { 0, 1 }; // x()
int dyp[4] = { 1, 0 }; // y()
using Weight = int;
using Flow = int;
struct Edge {
int src, dst;
// libalgo G[e.dst]
int rev;
Weight weight;
Flow cap;
Edge() : src(0), dst(0), weight(0) {}
Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;
void add_edge(Graph& g, int a, int b, Weight w = 1) {
g[a].emplace_back(a, b, w);
g[b].emplace_back(b, a, w);
}
void add_arc(Graph& g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }
// src dst (https://hello-world-494ec.firebaseapp.com/)
template <typename T>
void dump_graph(T G) {
int V = G.size();
int E = 0;
ostringstream os;
for (auto es : G) {
for (auto e : es) {
E++;
os << e.src << " " << e.dst << "\n";
}
}
cout << V << " " << E << "\n";
cout << os.str() << "\n";
}
//
// @pre: gH*W
void create_from_grid(Graph& g, int h, int w, vector<string>& mapData, char wall) {
// O(HW)
rep(y, h) {
rep(x, w) {
if (mapData[y][x] == wall) {
continue;
}
int id = y * w + x;
//()()
rep(i, 2) {
int nx = x + dxp[i];
int ny = y + dyp[i];
int nid = ny * w + nx;
if (nx < 0 || nx >= w) {
continue;
}
if (ny < 0 || ny >= h) {
continue;
}
if (mapData[ny][nx] != wall) {
add_edge(g, id, nid);
}
}
}
}
}
//
// @pre: gH*W
void create_weighted_from_grid(Graph& g, int h, int w, vector<vector<int>>& mapData) {
// O(HW)
rep(y, h) {
rep(x, w) {
int id = y * w + x;
// ()
rep(i, 4) {
int nx = x + dx[i];
int ny = y + dy[i];
int nid = ny * w + nx;
if (nx < 0 || nx >= w) {
continue;
}
if (ny < 0 || ny >= h) {
continue;
}
//
add_arc(g, id, nid, mapData[ny][nx]);
}
}
}
}
//
int point_to_node_num(int x, int y, int W) {
return y * W + x;
}
struct uf_tree {
std::vector<int> parent;
int __size;
uf_tree(int size_) : parent(size_, -1), __size(size_) {}
void unite(int x, int y) {
if ((x = find(x)) != (y = find(y))) {
if (parent[y] < parent[x]) std::swap(x, y);
parent[x] += parent[y];
parent[y] = x;
__size--;
}
}
bool is_same(int x, int y) { return find(x) == find(y); }
int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
int size(int x) { return -parent[find(x)]; }
int size() { return __size; }
};
//!!!!!!
//!!!!!!
//!!!!!!
template <signed M, unsigned T>
struct mod_int {
constexpr static signed MODULO = M;
constexpr static unsigned TABLE_SIZE = T;
signed x;
mod_int() : x(0) {}
mod_int(long long y) : x(static_cast<signed>(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO)) {}
mod_int(signed y) : x(y >= 0 ? y % MODULO : MODULO - (-y) % MODULO) {}
mod_int& operator+=(const mod_int& rhs) {
if ((x += rhs.x) >= MODULO) x -= MODULO;
return *this;
}
mod_int& operator-=(const mod_int& rhs) {
if ((x += MODULO - rhs.x) >= MODULO) x -= MODULO;
return *this;
}
mod_int& operator*=(const mod_int& rhs) {
x = static_cast<signed>(1LL * x * rhs.x % MODULO);
return *this;
}
mod_int& operator/=(const mod_int& rhs) {
x = static_cast<signed>((1LL * x * rhs.inv().x) % MODULO);
return *this;
}
mod_int operator-() const { return mod_int(-x); }
mod_int operator+(const mod_int& rhs) const { return mod_int(*this) += rhs; }
mod_int operator-(const mod_int& rhs) const { return mod_int(*this) -= rhs; }
mod_int operator*(const mod_int& rhs) const { return mod_int(*this) *= rhs; }
mod_int operator/(const mod_int& rhs) const { return mod_int(*this) /= rhs; }
bool operator<(const mod_int& rhs) const { return x < rhs.x; }
mod_int inv() const {
assert(x != 0);
if (x <= static_cast<signed>(TABLE_SIZE)) {
if (_inv[1].x == 0) prepare();
return _inv[x];
}
else {
signed a = x, b = MODULO, u = 1, v = 0, t;
while (b) {
t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return mod_int(u);
}
}
mod_int pow(long long t) const {
assert(!(x == 0 && t == 0));
mod_int e = *this, res = mod_int(1);
for (; t; e *= e, t >>= 1)
if (t & 1) res *= e;
return res;
}
mod_int fact() {
if (_fact[0].x == 0) prepare();
return _fact[x];
}
mod_int inv_fact() {
if (_fact[0].x == 0) prepare();
return _inv_fact[x];
}
mod_int choose(mod_int y) {
assert(y.x <= x);
return this->fact() * y.inv_fact() * mod_int(x - y.x).inv_fact();
}
static mod_int _inv[TABLE_SIZE + 1];
static mod_int _fact[TABLE_SIZE + 1];
static mod_int _inv_fact[TABLE_SIZE + 1];
static void prepare() {
_inv[1] = 1;
for (int i = 2; i <= (int)TABLE_SIZE; ++i) {
_inv[i] = 1LL * _inv[MODULO % i].x * (MODULO - MODULO / i) % MODULO;
}
_fact[0] = 1;
for (unsigned i = 1; i <= TABLE_SIZE; ++i) {
_fact[i] = _fact[i - 1] * signed(i);
}
_inv_fact[TABLE_SIZE] = _fact[TABLE_SIZE].inv();
for (int i = (int)TABLE_SIZE - 1; i >= 0; --i) {
_inv_fact[i] = _inv_fact[i + 1] * (i + 1);
}
}
};
template <signed M, unsigned F>
std::ostream& operator<<(std::ostream& os, const mod_int<M, F>& rhs) {
return os << rhs.x;
}
template <signed M, unsigned F>
std::istream& operator >> (std::istream& is, mod_int<M, F>& rhs) {
long long s;
is >> s;
rhs = mod_int<M, F>(s);
return is;
}
template <signed M, unsigned F>
mod_int<M, F> mod_int<M, F>::_inv[TABLE_SIZE + 1];
template <signed M, unsigned F>
mod_int<M, F> mod_int<M, F>::_fact[TABLE_SIZE + 1];
template <signed M, unsigned F>
mod_int<M, F> mod_int<M, F>::_inv_fact[TABLE_SIZE + 1];
template <signed M, unsigned F>
bool operator==(const mod_int<M, F>& lhs, const mod_int<M, F>& rhs) {
return lhs.x == rhs.x;
}
template <int M, unsigned F>
bool operator!=(const mod_int<M, F>& lhs, const mod_int<M, F>& rhs) {
return !(lhs == rhs);
}
const signed MF = 1000010;
const signed MOD = 1000000007;
using mint = mod_int<MOD, MF>;
mint binom(int n, int r) { return (r < 0 || r > n || n < 0) ? 0 : mint(n).choose(r); }
mint fact(int n) { return mint(n).fact(); }
mint inv_fact(int n) { return mint(n).inv_fact(); }
// http://beet-aizu.hatenablog.com/entry/2017/12/01/225955
/*
int n_
f
2T
MAX: max
SumAdd: +
g
1TE
MAX: =
SumAdd: +
h
2E
MAX: =
SumAdd: +
T d1
f
MAX: -INF 
SumAdd: 0
E d0,
g, h
MAX:
SumAdd: 0
vector<T> v = vector<T>()
vector
P p = [](E a, int b) {return a; }
bE'
MAXAdd
SumAdd: *
//
//chmin, min
auto myMin = [](int a, int b) {return min(a, b); };
SegmentTree<int, int> seg(n, myMin, myMin, myMin, LL_HALFMAX, LL_HALFMAX);
//updatemin
SegmentTree<int, int> seg(n, myMin, myMin, myMin, LL_HALFMAX, LL_HALFMAX);
//AddSum
vector<int> v(0, N + 1);
SegmentTree<int, int> segtree(N + 1, plus<int>(), plus<int>(), plus<int>(), 0, 0, v, [](int a, int b) {return a * b; });
//AddMin
vector<int> v(0, N + 1);
SegmentTree<int, int> segtree(N + 1, myMin, plus<int>(), plus<int>(), LL_HALFMAX, 0, v, [](int a, int b) {return a; });
*/
template <typename T, typename E>
struct SegmentTree {
typedef function<T(T, T)> F;
typedef function<T(T, E)> G;
typedef function<E(E, E)> H;
typedef function<E(E, int)> P;
int n;
F f;
G g;
H h;
P p;
T d1;
E d0;
vector<T> dat;
vector<E> laz;
SegmentTree(int n_, F f, G g, H h, T d1, E d0,
vector<T> v = vector<T>(), P p = [](E a, int b) {return a; }) :
f(f), g(g), h(h), d1(d1), d0(d0), p(p) {
init(n_);
if (n_ == (int)v.size()) build(n_, v);
}
//2*n-1
void init(int n_) {
n = 1;
while (n < n_) n *= 2;
dat.clear();
dat.resize(2 * n - 1, d1);
laz.clear();
laz.resize(2 * n - 1, d0);
}
//vector
void build(int n_, vector<T> v) {
for (int i = 0; i < n_; i++) dat[i + n - 1] = v[i];
for (int i = n - 2; i >= 0; i--)
dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);
}
//
inline void eval(int len, int k) {
//
if (laz[k] == d0) return;
//
if (k * 2 + 1 < n * 2 - 1) {
//h: 2
laz[k * 2 + 1] = h(laz[k * 2 + 1], laz[k]);
laz[k * 2 + 2] = h(laz[k * 2 + 2], laz[k]);
}
//p:
//dat[k] laz (g:
            SumAdd (+ 3) )
dat[k] = g(dat[k], p(laz[k], len));
//
laz[k] = d0;
}
//[l,r)0-indexed[a, b)
T update(int a, int b, E x, int k, int l, int r) {
//
eval(r - l, k);
//
if (r <= a || b <= l) return dat[k];
//p
            
if (a <= l && r <= b) {
laz[k] = h(laz[k], x);
return g(dat[k], p(laz[k], r - l));
}
//()
return dat[k] = f(update(a, b, x, k * 2 + 1, l, (l + r) / 2),
update(a, b, x, k * 2 + 2, (l + r) / 2, r));
}
T update(int a, int b, E x) {
return update(a, b, x, 0, 0, n);
}
T update(int a, E x) {
return update(a, a + 1, x);
}
T query(int a, int b, int k, int l, int r) {
eval(r - l, k);
//
if (r <= a || b <= l) return d1;
//
if (a <= l && r <= b) return dat[k];
//
T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return f(vl, vr);
}
//0-indexed[a, b)*
T query(int a, int b) {
return query(a, b, 0, 0, n);
}
T query(int a) {
return query(a, a + 1, 0, 0, n);
}
void debug_print(int num) {
vector<T> v;
rep(i, num) {
v.push_back(query(i));
}
cout << "{" << v << "}\n";
}
};
//
class compress {
public:
map<int, int> zip;
vector<int> unzip;
compress(vector<int> x)
{
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for (int i = 0; i < x.size(); i++) {
zip[x[i]] = i;
unzip.push_back(x[i]);
}
}
};
int euclidean_gcd(int a, int b) {
while (1) {
if (a < b) swap(a, b);
if (!b) break;
a %= b;
}
return a;
}
//https://ei1333.github.io/luzhiled/snippets/dp/cumulative-sum-2d.html
template< class T >
struct CumulativeSum2D {
vector< vector< T > > data;
CumulativeSum2D(int W, int H) : data(W + 1, vector< int >(H + 1, 0)) {}
void add(int x, int y, T z) {
++x, ++y;
if (x >= data.size() || y >= data[0].size()) return;
data[x][y] += z;
}
void build() {
for (int i = 1; i < data.size(); i++) {
for (int j = 1; j < data[i].size(); j++) {
data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
}
}
}
T query(int sx, int sy, int gx, int gy) {
return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
}
};
// imos 2D
template<class T>
class Imos2D {
private:
vector< vector< T > > m_Data;
int m_W, m_H;
bool m_Built;
public:
Imos2D(int W, int H)
: m_Data(H + 1, vector< T >(W + 1, 0))
, m_W(W)
, m_H(H)
, m_Built(false)
{}
// [(sx, sy), (tx, ty)) add ()
void RangeAdd(int sx, int sy, int tx, int ty, int add) {
assert(!m_Built);
m_Data[sy][sx]++; //
m_Data[sy][tx]--; //
m_Data[ty][sx]--; //
m_Data[ty][tx]++; //
}
void Build() {
assert(!m_Built);
//
for (int y = 0; y < m_H; y++) {
for (int x = 1; x < m_W; x++) {
m_Data[y][x] += m_Data[y][x - 1];
}
}
//
for (int y = 1; y < m_H; y++) {
for (int x = 0; x < m_W; x++) {
m_Data[y][x] += m_Data[y - 1][x];
}
}
m_Built = true;
}
int Get(int x, int y) {
assert(m_Built);
return m_Data[y][x];
}
};
//
// TORIAEZU:
/*
template< class T >
class CumulativeSum2D {
private:
//
vector<vector<T>> m_Data;
int m_Height;
int m_Width;
//
vector<vector<T>> m_Cum;
public:
CumulativeSum2D(int H, int W) :
m_Cum(H+1, vector<int>(W+1, 0)),
m_Height(H),
m_Width(W)
{}
// TORIAEZU:
CumulativeSum2D(vector<vector<T>> inputData) :
m_Data(inputData),
m_Height(static_cast<int>(inputData.size())),
m_Width(static_cast<int>(inputData[0].size())),
m_Cum(m_Height + 1, vector<int>(m_Width + 1, 0))
{
}
// 0-indexed
void Change(int x, int y, T val) {
assert(x < m_Width);
assert(y < m_Height);
m_Data[y][x] = val;
}
void Build() {
for (int i = 0; i < m_Height; i++) {
for (int j = 0; j < m_Width; j++) {
m_Cum[i + 1][j + 1] = m_Cum[i][j + 1] + m_Cum[i + 1][j] - m_Cum[i][j] + m_Data[i][j];
}
}
}
// [sx, gx), [sy, gy)
T Query(int sx, int sy, int gx, int gy) {
return m_Cum[gy][gx] - m_Cum[sy][gx] - m_Cum[gy][sx] + m_Cum[sy][sx];
}
};
*/
//lib
int nC2(int n) {
return n * (n - 1) / 2;
}
class node {
public:
int depth;
int num;
node(int d, int n) {
depth = d;
num = n;
}
};
template< class T >
struct CumulativeSum {
vector< T > data;
CumulativeSum(int sz) : data(sz, 0) {};
void add(int k, T x) {
data[k] += x;
}
void build() {
for (int i = 1; i < data.size(); i++) {
data[i] += data[i - 1];
}
}
T query(int k) {
if (k < 0) return (0);
return (data[min(k, (int)data.size() - 1)]);
}
//[left, right]
T query(int left, int right) {
return query(right) - query(left - 1);
}
};
std::vector<int> eratosthenes_sieve(int n) {
std::vector<int> ps(n + 1);
std::iota(ps.begin() + 2, ps.end(), 2);
for (int i = 2; i * i <= n; ++i)
if (ps[i])
for (int j = i * i; j <= n; j += i) ps[j] = 0;
return ps;
}
std::vector<int> make_primes(int n) {
std::vector<int> ps = eratosthenes_sieve(n);
ps.erase(std::remove(ps.begin(), ps.end(), 0), ps.end());
return ps;
}
// [a, b)is_prime[i]: a + i or not is_prime[i-a] true: i
std::vector<bool> segment_eratosthenes_sieve(int a, int b) {
vector<bool> is_prime(b - a, true);
vector<bool> is_prime_small;
for (int i = 0; i*i < b; i++)is_prime_small.push_back(true);
for (int i = 2; i*i < b; i++) {
if (is_prime_small[i]) {
for (int j = 2 * i; j*j < b; j += i) {
is_prime_small[j] = false; // [2, sqrt(b))
}
// (a + i - 1LL) / i * i ai
for (int j = max(2LL, (a + i - 1LL) / i) * i; j < b; j += i) {
is_prime[j - a] = false; // [a, b)
}
}
}
return is_prime;
}
vector< int64_t > divisor(int64_t n) {
vector< int64_t > ret;
for (int64_t i = 1; i * i <= n; i++) {
if (n % i == 0) {
ret.push_back(i);
if (i * i != n) ret.push_back(n / i);
}
}
sort(begin(ret), end(ret));
return (ret);
}
// ()
int binary_search(function<bool(int)> isOk, int ng, int ok) {
/* ok ng */
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (isOk(mid)) ok = mid;
else ng = mid;
}
return ok;
}
std::pair<std::vector<Weight>, bool> bellmanFord(const Graph& g, int s) {
int n = g.size();
const Weight inf = std::numeric_limits<Weight>::max() / 8;
Edges es;
for (int i = 0; i < n; i++)
for (auto& e : g[i]) es.emplace_back(e);
//
std::vector<Weight> dist(n, inf);
dist[s] = 0;
bool negCycle = false;
for (int i = 0;; i++) {
bool update = false;
//
for (auto& e : es) {
if (dist[e.src] != inf && dist[e.dst] > dist[e.src] + e.weight) {
dist[e.dst] = dist[e.src] + e.weight;
update = true;
}
}
//
if (!update) break;
//n
if (i > n) {
negCycle = true;
break;
}
}
return std::make_pair(dist, !negCycle);
}
//OK()
std::pair<std::vector<Weight>, bool> bellmanFord(const Graph& g, int s, int d) {
int n = g.size();
const Weight inf = std::numeric_limits<Weight>::max() / 8;
Edges es;
for (int i = 0; i < n; i++)
for (auto& e : g[i]) es.emplace_back(e);
//
std::vector<Weight> dist(n, inf);
dist[s] = 0;
bool negCycle = false;
for (int i = 0; i < n * 2; i++) {
bool update = false;
//
for (auto& e : es) {
if (dist[e.src] != inf && dist[e.dst] > dist[e.src] + e.weight) {
// n d NG
if (i >= n - 1 && e.dst == d) {
negCycle = true;
}
//
else if (i >= n - 1) {
dist[e.dst] = -inf;
update = true;
}
else {
dist[e.dst] = dist[e.src] + e.weight;
update = true;
}
}
}
//
if (!update) break;
}
return std::make_pair(dist, !negCycle);
}
//R[i] == S[i] vector R
vector<int> Manachar(string S) {
int len = S.length();
vector<int> R(len);
int i = 0, j = 0;
while (i < S.size()) {
while (i - j >= 0 && i + j < S.size() && S[i - j] == S[i + j]) ++j;
R[i] = j;
int k = 1;
while (i - k >= 0 && i + k < S.size() && k + R[i - k] < j) R[i + k] = R[i - k], ++k;
i += k; j -= k;
}
return R;
}
std::vector<int> tsort(const Graph &g) {
int n = g.size(), k = 0;
std::vector<int> ord(n), in(n);
for (auto &es : g)
for (auto &e : es) in[e.dst]++;
std::queue<int> q;
//0
for (int i = 0; i < n; ++i)
if (in[i] == 0) q.push(i);
while (q.size()) {
int v = q.front();
//S node n
q.pop();
//L n
ord[k++] = v;
for (auto &e : g[v]) {
//0
if (--in[e.dst] == 0) {
q.push(e.dst);
}
}
}
return *std::max_element(in.begin(), in.end()) == 0 ? ord : std::vector<int>();
}
std::vector<Weight> dijkstra(const Graph &g, int s) {
const Weight INF = std::numeric_limits<Weight>::max() / 8;
using state = std::tuple<Weight, int>;
std::priority_queue<state> q;
std::vector<Weight> dist(g.size(), INF);
dist[s] = 0;
q.emplace(0, s);
while (q.size()) {
Weight d;
int v;
std::tie(d, v) = q.top();
q.pop();
d *= -1;
/* if(v == t) return d; */
if (dist[v] < d) continue;
for (auto &e : g[v]) {
if (dist[e.dst] > dist[v] + e.weight) {
dist[e.dst] = dist[v] + e.weight;
q.emplace(-dist[e.dst], e.dst);
}
}
}
return dist;
}
Matrix WarshallFloyd(const Graph &g) {
auto const INF = std::numeric_limits<Weight>::max() / 8;
int n = g.size();
Matrix d(n, Array(n, INF));
rep(i, n) d[i][i] = 0;
rep(i, n) for (auto &e : g[i]) d[e.src][e.dst] = std::min(d[e.src][e.dst], e.weight);
rep(k, n) rep(i, n) rep(j, n) {
if (d[i][k] != INF && d[k][j] != INF) d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}
return d;
}
std::pair<std::vector<int>, std::vector<int>> prime_factor_decomp(int n) {
std::vector<int> p, e;
int m = n;
for (int i = 2; i * i <= n; i++) {
if (m % i != 0) continue;
int c = 0;
while (m % i == 0) c++, m /= i;
p.push_back(i);
e.push_back(c);
}
if (m > 1) {
p.push_back(m);
e.push_back(1);
}
return std::make_pair(p, e);
}
int extgcd(int a, int b, int &x, int &y) {
int g = a;
x = 1;
y = 0;
if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
return g;
}
// ax + by = c (pt + q, rt + s)
/*
* exist:
* p, q, r, s: (pt + q, rt + s)
* p > 0 q < 0 ()
*/
void IndeterminateEq(int a, int b, int c, bool& exist, int& p, int& q, int& r, int& s) {
int X, Y;
int g = euclidean_gcd(a, b);
// c NG
if (c % g != 0) {
exist = false;
return;
}
exist = true;
// ax + by = gcd(a, b) (X, Y)
extgcd(a, b, X, Y);
int m = c / g;
// ax + by = c
X *= m;
Y *= m;
int a2 = a / g;
int b2 = b / g;
p = b2;
q = X;
r = -a2;
s = Y;
}
// x^n mod modulo
// n 2^k -> n kbit(0-indexed)x^k
int mod_pow(int x, int n, int modulo) {
int res = 1;
while (n > 0) {
if (n & 1) {
res = res * x % modulo;
}
x = x * x % modulo;
n >>= 1;
}
return res;
}
int64_t popcnt(int64_t n)
{
int64_t c = 0;
c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333);
c = (c & 0x0f0f0f0f0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f0f0f0f0f);
c = (c & 0x00ff00ff00ff00ff) + ((c >> 8) & 0x00ff00ff00ff00ff);
c = (c & 0x0000ffff0000ffff) + ((c >> 16) & 0x0000ffff0000ffff);
c = (c & 0x00000000ffffffff) + ((c >> 32) & 0x00000000ffffffff);
return(c);
}
// 2D
// 90
const vector<vector<int>> AntiClockWiseMatrix90 = {
{0, 1, 0},
{-1, 0, 0},
{0, 0, 1}
};
// 90
vector<vector<int>> ClockWiseMatrix90 = {
{0, -1, 0},
{1, 0, 0},
{0, 0, 1}
};
// x x y y ,
const auto MoveMat = [](int x, int y) -> vector<vector<int>> {
return vector<vector<int>> {
{1, 0, 0},
{0, 1, 0},
{x, y, 1}
};
};
// X -> y
const vector<vector<int>> ReflectionX = {
{1, 0, 0},
{0, -1, 0},
{0, 0, 1}
};
// Y -> x
const vector<vector<int>> ReflectionY = {
{-1, 0, 0},
{0, 1, 0},
{0, 0, 1}
};
//
const vector<vector<int>> IdentityMatrix = {
{1, 0, 0},
{0, 1, 0},
{0, 0, 1}
};
/*
vector<vector<T>> matrixMultiplies(vector<vector<T>> l, vector<vector<T>> r, F plus = plus<T>(), G multiple = multiplies<T>(), T eplus = 0LL)
vector<vector<T>> matrixPower(vector<vector<T>> m, int n, F plus = std::plus<T>(), G multiple = multiplies<T>(), T eplus = 0LL, T emultiple = 1LL)
(N, +, *) l, r
T: ()
l:
r:
plus:
multiple:
eplus:
emultiple:
*/
template<typename T = long long, typename F = decltype(std::plus<T>()), typename G = decltype(multiplies<T>())>
vector<vector<T>> matrixMultiplies(vector<vector<T>> l, vector<vector<T>> r, F plus = plus<T>(), G multiple = multiplies<T>(), T eplus = 0LL) {
int rx = r[0].size();
int ry = r.size();
int ly = l.size();
int lx = l[0].size();
assert(lx == ry);
vector<vector<T> > ret;
for (int y = 0; y < ly; y++) {
vector<T> add;
for (int x = 0; x < rx; x++) {
T cell = eplus;
for (int i = 0; i < ry; i++) {
T mul = multiple(l[y][i], r[i][x]);
cell = plus(cell, mul);
}
add.push_back(cell);
}
ret.push_back(add);
}
return ret;
}
template<typename T = long long, typename F = decltype(std::plus<T>()), typename G = decltype(multiplies<T>())>
vector<vector<T>> matrixPower(vector<vector<T>> m, int n, F plus = std::plus<T>(), G multiple = multiplies<T>(), T eplus = 0LL, T emultiple = 1LL) {
int k = m.size();
if (n == 0) {
vector<vector<T> > E;
for (int i = 0; i < k; i++) {
//
vector<T> v(k, eplus);
v[i] = emultiple;
E.push_back(v);
}
return E;
}
vector<vector<T>> ret = matrixPower(matrixMultiplies(m, m, plus, multiple, eplus), n / 2, plus, multiple, eplus, emultiple);
if (n % 2 == 1) {
ret = matrixMultiplies(m, ret, plus, multiple);
}
return ret;
}
//
//
/*
Ford-Fulkerson() O(F|E|)
F:
E:
nadd_edge
*/
class Ford_Fulkerson {
private:
struct Edge {
int src, dst;
// libalgo G[e.dst]
int rev;
int cap;
Edge(int s, int d, int c, int r) : src(s), dst(d), cap(c), rev(r) {}
};
vector<vector<Edge> > G;
vector<bool> used;
public:
Ford_Fulkerson(int n) :
G(n),
used(n, false)
{}
void add_edge(int s, int d, int cap) {
G[s].emplace_back(s, d, cap, G[d].size());
G[d].emplace_back(d, s, 0, G[s].size() - 1);
}
int dfs(int v, int t, int f) {
if (v == t) {
return f;
}
used[v] = true;
for (Edge& e : G[v]) {
if (!used[e.dst] && e.cap > 0) {
//
int d = dfs(e.dst, t, min(f, e.cap));
if (d > 0) {
//
e.cap -= d;
//
G[e.dst][e.rev].cap += d;
return d;
}
}
}
// t 0
return 0;
}
int max_flow(int s, int t) {
int flow = 0;
while (1) {
for (int i = 0; i < used.size(); i++) {
used[i] = false;
}
int f = dfs(s, t, LL_HALFMAX);
if (f == 0) {
return flow;
}
flow += f;
}
}
};
/*
Dinic From libalgo O(V^2 * E)
dinic::solve(s, t) : s -> t
dinic;;flow[u][v] : (u, v)
*/
struct dinic {
int n, s, t;
std::vector<int> level, prog, que;
std::vector<std::vector<Flow>> cap, flow;
std::vector<std::vector<int>> g;
Flow inf;
dinic(const Graph &graph)
: n(graph.size()),
cap(n, std::vector<Flow>(n)),
flow(n, std::vector<Flow>(n)),
g(n, std::vector<int>()),
inf(std::numeric_limits<Flow>::max() / 8) {
for (int i = 0; i < n; i++) {
for (auto &e : graph[i]) {
int u = e.src, v = e.dst;
Flow c = e.cap;
cap[u][v] += c;
cap[v][u] += c;
flow[v][u] += c;
g[u].push_back(v);
g[v].push_back(u);
}
}
}
//
inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
//
Flow solve(int s_, int t_) {
this->t = t_, this->s = s_;
que.resize(n + 1);
Flow res = 0;
// levelize() == false: bfs s t
while (levelize()) {
prog.assign(n, 0);
res += augment(s, inf);
}
return res;
}
// bfs
bool levelize() {
int l = 0, r = 0;
level.assign(n, -1);
level[s] = 0;
que[r++] = s;
while (l != r) {
int v = que[l++];
if (v == t) break;
for (const int &d : g[v]) {
// v -> dlevel[d] = level[v] + 1
if (level[d] == -1 && residue(v, d) != 0) {
level[d] = level[v] + 1;
que[r++] = d;
}
}
}
// t true
return level[t] != -1;
}
// dfs
Flow augment(int v, Flow lim) {
Flow res = 0;
if (v == t) return lim;
// prog[v]: dfs vv
for (int &i = prog[v]; i < (int)g[v].size(); i++) {
const int &d = g[v][i];
// v -> d or v() (=)NG
if (residue(v, d) == 0 || level[v] >= level[d]) continue;
//
const Flow aug = augment(d, std::min(lim, residue(v, d)));
flow[v][d] += aug;
flow[d][v] -= aug;
res += aug;
lim -= aug;
// v使
if (lim == 0) break;
}
return res;
}
};
/*
Primal-Dual( / )
*/
class Primal_Dual_BellmanFord {
using Cost = int;
struct Edge {
int src, dst;
// libalgo G[e.dst]
int rev;
Cost cost;
Flow cap;
Edge(int s, int d, int aRev, Cost aCost, Flow aCap) : src(s), dst(d), rev(aRev), cost(aCost), cap(aCap) {}
};
int V; //
vector<vector<Edge>> G; //
vector<int> dist; //
vector<int> prevv; //
vector<int> preve; //
const int INF;
public:
// n
Primal_Dual_BellmanFord(int n) :
V(n),
G(n),
dist(n, 0),
prevv(n, 0),
preve(n, 0),
INF(std::numeric_limits<int>::max() / 8) {}
void add_edge(int src, int dst, int cap, int cost) {
// cost weight
G[src].emplace_back(src, dst, G[dst].size(), cost, cap);
G[dst].emplace_back(dst, src, G[src].size() - 1, -cost, 0);
}
int min_cost_flow(int s, int t, int f) {
int res = 0;
while (f > 0) {
// s-t
dist.assign(V, INF);
dist[s] = 0;
bool update = true;
while (update) {
update = false;
for (int v = 0; v < V; v++) {
if (dist[v] == INF) continue;
for (int i = 0; i < G[v].size(); i++) {
Edge& e = G[v][i];
if (e.cap > 0 && dist[e.dst] > dist[v] + e.cost) {
dist[e.dst] = dist[v] + e.cost;
prevv[e.dst] = v;
preve[e.dst] = i;
update = true;
}
}
}
}
//
if (dist[t] == INF) {
return -1;
}
// s-t沿
int d = f;
// prevv辿
for (int v = t; v != s; v = prevv[v]) {
//
Edge &e = G[prevv[v]][preve[v]];
chmin(d, e.cap);
}
f -= d;
// dist
res += d * dist[t];
for (int v = t; v != s; v = prevv[v]) {
Edge &e = G[prevv[v]][preve[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
return res;
}
};
/*
Primal-Dual
: https://ei1333.github.io/luzhiled/snippets/graph/primal-dual.html
*/
template< typename flow_t, typename cost_t >
struct PrimalDual {
const cost_t INF;
struct edge {
int to;
flow_t cap;
cost_t cost;
int rev;
bool isrev;
edge(int aTo, flow_t aCap, cost_t aCost, int aRev, bool aIsRev) : to(aTo), cap(aCap), cost(aCost), rev(aRev), isrev(aIsRev) {}
};
vector< vector< edge > > graph;
vector< cost_t > potential, min_cost;
vector< int > prevv, preve;
PrimalDual(int V) : graph(V), INF(numeric_limits< cost_t >::max()) {}
void add_edge(int from, int to, flow_t cap, cost_t cost) {
graph[from].emplace_back(to, cap, cost, (int)graph[to].size(), false);
graph[to].emplace_back(from, 0, -cost, (int)graph[from].size() - 1, true);
}
cost_t min_cost_flow(int s, int t, flow_t f) {
int V = (int)graph.size();
cost_t ret = 0;
using Pi = pair< cost_t, int >;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
potential.assign(V, 0);
preve.assign(V, -1);
prevv.assign(V, -1);
while (f > 0) {
min_cost.assign(V, INF);
que.emplace(0, s);
min_cost[s] = 0;
while (!que.empty()) {
Pi p = que.top();
que.pop();
if (min_cost[p.second] < p.first) continue;
for (int i = 0; i < graph[p.second].size(); i++) {
edge &e = graph[p.second][i];
cost_t nextCost = min_cost[p.second] + e.cost + potential[p.second] - potential[e.to];
if (e.cap > 0 && min_cost[e.to] > nextCost) {
min_cost[e.to] = nextCost;
prevv[e.to] = p.second, preve[e.to] = i;
que.emplace(min_cost[e.to], e.to);
}
}
}
if (min_cost[t] == INF) return -1;
for (int v = 0; v < V; v++) potential[v] += min_cost[v];
flow_t addflow = f;
for (int v = t; v != s; v = prevv[v]) {
addflow = min(addflow, graph[prevv[v]][preve[v]].cap);
}
f -= addflow;
ret += addflow * potential[t];
for (int v = t; v != s; v = prevv[v]) {
edge &e = graph[prevv[v]][preve[v]];
e.cap -= addflow;
graph[v][e.rev].cap += addflow;
}
}
return ret;
}
void output() {
for (int i = 0; i < graph.size(); i++) {
for (auto &e : graph[i]) {
if (e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << rev_e.cap + e.cap << ")" << endl;
}
}
}
};
class lca {
public:
int n, segn;
vector<int> path; // vs
vector<int> depth; // depthpath[i]
vector<int> in_order; // idi
vector<pair<int, int>> dat;
const std::pair<int, int> INF = std::make_pair(1000000000, 1000000000);
lca(const Graph& g, int root) : n(g.size()), path(n * 2 - 1), depth(n * 2 - 1), in_order(n) {
int k = 0;
dfs(g, root, -1, 0, k);
// pair(depth, index) => depth index
for (segn = 1; segn < n * 2 - 1; segn <<= 1);
dat.assign(segn * 2, INF);
for (int i = 0; i < (int)depth.size(); ++i) dat[segn + i] = std::make_pair(depth[i], i);
for (int i = segn - 1; i >= 1; --i) dat[i] = min(dat[i * 2], dat[i * 2 + 1]);
}
int get(int u, int v) const {
int l = std::min(in_order[u], in_order[v]);
int r = std::max(in_order[u], in_order[v]) + 1;
return path[range_min(1, segn, l, r).second];
}
void dfs(const Graph& g, int v, int p, int d, int& k) {
// k:
in_order[v] = k;
path[k] = v;
depth[k++] = d;
for (auto &e : g[v]) {
if (e.dst != p) {
dfs(g, e.dst, v, d + 1, k);
// ve.dstv path depth
path[k] = v;
depth[k++] = d;
}
}
}
// v : w: l: ? r: ?
pair<int, int> range_min(int v, int w, int l, int r) const {
if (r <= l || w == 0) return INF;
if (r - l == w)
return dat[v];
int m = w / 2;
auto rmin = range_min(v * 2, m, l, std::min(r, m));
auto lmin = range_min(v * 2 + 1, m, std::max(0LL, l - m), r - m);
return min(rmin, lmin);
}
};
// int ceil floor(a / b ceil, floor)
int64_t intceil(int64_t a, int64_t b) {
int sign_a = (a > 0) - (a < 0);
int sign_b = (b > 0) - (b < 0);
if (sign_a == sign_b) {
return (a + b - sign_b) / b;
}
else {
return a / b;
}
}
int64_t intfloor(int64_t a, int64_t b) {
int sign_a = (a > 0) - (a < 0);
int sign_b = (b > 0) - (b < 0);
if (sign_a == sign_b) {
return a / b;
}
else {
return (a - b + sign_b) / b;
}
}
class Point {
public:
int y, x;
Point() { y = x = 0; }
Point(int y0, int x0) {
y = y0;
x = x0;
}
Point operator+(const Point& p) const { return Point(y + p.y, x + p.x); }
Point operator-(const Point& p) const { return Point(y - p.y, x - p.x); }
Point operator*(int a) const { return Point(y * a, x * a); }
long long length2() const { return y * (long long)y + x * (long long)x; }
long long dist2(const Point& p) const {
return (y - p.y) * (long long)(y - p.y) + (x - p.x) * (long long)(x - p.x);
}
long long dot(const Point& p) const {
return y * (long long)p.y + x * (long long)p.x; // |a|*|b|*cosθ
}
long long cross(const Point& p) const {
return x * (long long)p.y - y * (long long)p.x; // |a|*|b|*sinθ
}
static bool Sorter(const Point& p1, const Point& p2) {
bool a = p1.y > 0 || (p1.y == 0 && p1.x >= 0);
bool b = p2.y > 0 || (p2.y == 0 && p2.x >= 0);
if (a != b) return a;
long long c = p2.x * (long long)p1.y;
long long d = p1.x * (long long)p2.y;
if (c != d) return c < d;
return p1.length2() < p2.length2();
}
};
//
template<typename T>
vector<pair<T, int>> RunLength(vector<T> arr) {
T now = arr[0];
int len = arr.size();
vector<pair<T, int>> res;
int cnt = 0;
rep(i, len) {
if (arr[i] != now) {
res.emplace_back(now, cnt);
now = arr[i];
cnt = 0;
}
cnt++;
}
res.push_back(mp(now, cnt));
return res;
}
// ref: https://ei1333.github.io/luzhiled/snippets/memo/doubling.html
// op MSVC clz
// -> SetNext -> Build -> Query
class Doubling
{
private:
int m_LogMax;
vector<vector<int>> m_Next;
// op (: )
std::function<int(int, int)> m_Op;
// op
int m_E;
// TODO: std::optional 使( C++17 使)
const bool m_HasOp;
// m_RangeOp[k][i] := [i, i+2^k) op
vector<vector<int>> m_RangeOp;
public:
/**
* @fn
* @brief op N, queryMax Doubling op op
* @param N
* @param queryMax
*/
Doubling(int N, int queryMax)
: m_HasOp(false)
{
m_LogMax = 1;
while ((1LL << m_LogMax) < queryMax) {
m_LogMax++;
}
// m_LogMax * N
m_Next.assign(m_LogMax, vector<int>(N, -1));
}
/**
* @fn
* @brief op N, queryMax Doubling op 使 op
* @param N
* @param queryMax
* @param op (: +)
* @param e op (: 0)
*/
Doubling(int N, int queryMax, function<int(int, int)> op, int e)
: m_Op(op)
, m_E(e)
, m_HasOp(true)
{
m_LogMax = 1;
while ((1LL << m_LogMax) < queryMax) {
m_LogMax++;
}
// m_LogMax * N
m_Next.assign(m_LogMax, vector<int>(N, -1));
m_RangeOp.assign(m_LogMax, vector<int>(N, 0));
}
/**
* @fn
* @brief k 1
* @param k
* @param x
*/
void SetNext(int k, int x) {
m_Next[0][k] = x;
}
/**
* @fn
* @brief Doubling
* @pre 1SetNext
*/
void Build() {
// k + 1 k + 1 < m_LogMax
for (int k = 0; k + 1 < m_LogMax; k++) {
for (int i = 0; i < m_Next[k].size(); i++) {
// i 2^k 2^(k+1)
if (m_Next[k][i] == -1) {
m_Next[k + 1][i] = -1;
}
else {
// i 2^(k+1) i 2^k 2^k
m_Next[k + 1][i] = m_Next[k][m_Next[k][i]];
}
}
}
// op op
if (m_HasOp) {
// TORIAEZU: [i, i+1) op i
for (int i = 0; i < m_RangeOp[0].size(); i++) {
m_RangeOp[0][i] = i;
}
for (int k = 0; k + 1 < m_LogMax; k++) {
for (int i = 0; i < m_Next[k].size(); i++) {
// op ()
// TODO: verify
assert(m_Next[k][i] != -1);
m_RangeOp[k + 1][i] = m_Op(m_RangeOp[k][i], m_RangeOp[k][m_Next[k][i]]);
}
}
}
}
/**
* @fn
* @brief k t
* @param k
* @param t
*/
int Query(int k, int t) {
for (int i = m_LogMax - 1; i >= 0; i--) {
if ((t >> i) & 1LL) {
k = m_Next[i][k];
}
}
return k;
}
/**
* @fn
* @brief k t A_0, A_1..., A_t{op(A_i), i = [0, t)} op
* @param k
* @param t
* @detail op = plus<int>, e = 0 verify
*/
int QueryRangeOp(int k, int t) {
assert(m_HasOp);
int ans = m_E;
for (int i = m_LogMax - 1; i >= 0; i--) {
if ((t >> i) & 1LL) {
ans = m_Op(ans, m_RangeOp[i][k]);
k = m_Next[i][k];
}
}
return ans;
}
};
// Vector2D
class Vector2D {
private:
double EPS = 1e-10;
//
double add(double a, double b) {
if (abs(a + b) < EPS * (abs(a) + abs(b))) {
return 0;
}
return a + b;
}
public:
double x, y;
Vector2D()
: x(0.0)
, y(0.0)
{}
Vector2D(double x, double y)
: x(x)
, y(y)
{}
Vector2D operator+(Vector2D p) {
return Vector2D(add(x, p.x), add(y, p.y));
}
Vector2D operator-(Vector2D p) {
return Vector2D(add(x, -p.x), add(y, -p.y));
}
Vector2D operator*(double d) {
return Vector2D(x * d, y * d);
}
Vector2D operator/(double d) {
return Vector2D(x / d, y / d);
}
// this dot p
double dot(Vector2D p) {
return add(x * p.x, y * p.y);
}
// this cross p
// z double
double cross(Vector2D p) {
return add(x * p.y, -y * p.x);
}
//
double SquareLength() {
return x * x + y * y;
}
//
double Length() {
return sqrtl(x * x + y * y);
}
// ()
Vector2D Rotate(double rad) {
Vector2D ret;
ret.x = x * cosl(rad) - y * sinl(rad);
ret.y = x * sinl(rad) + y * cosl(rad);
return ret;
}
// p1-p2q
static bool on_seg(Vector2D p1, Vector2D p2, Vector2D q) {
return (p1 - q).cross(p2 - q) == 0 && (p1 - q).dot(p2 - q) <= 0;
}
// p1-p2 q1-q2
static Vector2D intersection(Vector2D p1, Vector2D p2, Vector2D q1, Vector2D q2) {
return p1 + (p2 - p1) * ((q2 - q1).cross(q1 - p1) / (q2 - q1).cross(p2 - p1));
}
// pq rs
static bool is_intersect(Vector2D p, Vector2D q, Vector2D r, Vector2D s) {
Vector2D pq = q - p;
Vector2D rs = s - r;
// pq rs
if (pq.cross(rs) == 0) {
//
return on_seg(p, q, r) || on_seg(p, q, s) || on_seg(r, s, p) || on_seg(r, s, q);
}
//
else {
//
Vector2D i = intersection(p, q, r, s);
// OK
return on_seg(p, q, i) && on_seg(r, s, i);
}
}
};
// (P234)
vector<Vector2D> ConvexHull(vector<Vector2D> ps) {
int n = ps.size();
//
auto cmp_x = [](const Vector2D& p, const Vector2D& q) {
if (p.x != q.x) {
return p.x < q.x;
}
return p.y < q.y;
};
sort(ps.begin(), ps.end(), cmp_x);
int k = 0; //
vector<Vector2D> qs(n * 2); //
//
for (int i = 0; i < n; i++) {
// -> ->
while (k > 1 && (qs[k - 1] - qs[k - 2]).cross(ps[i] - qs[k - 1]) <= 0) {
k--;
}
qs[k++] = ps[i];
}
//
for (int i = n - 2, t = k; i >= 0; i--) {
while (k > t && (qs[k - 1] - qs[k - 2]).cross(ps[i] - qs[k - 1]) <= 0) {
k--;
}
qs[k++] = ps[i];
}
qs.resize(k - 1);
return qs;
}
struct SuccinctIndexableDictionary {
size_t length;
size_t blocks;
vector< unsigned > bit, sum;
SuccinctIndexableDictionary() = default;
SuccinctIndexableDictionary(size_t length) : length(length), blocks((length + 31) >> 5) {
bit.assign(blocks, 0U);
sum.assign(blocks, 0U);
}
void set(int k) {
bit[k >> 5] |= 1U << (k & 31);
}
void build() {
sum[0] = 0U;
for (int i = 1; i < blocks; i++) {
sum[i] = sum[i - 1] + popcnt(bit[i - 1]);
}
}
bool operator[](int k) {
return (bool((bit[k >> 5] >> (k & 31)) & 1));
}
int rank(int k) {
return (sum[k >> 5] + popcnt(bit[k >> 5] & ((1U << (k & 31)) - 1)));
}
int rank(bool val, int k) {
return (val ? rank(k) : k - rank(k));
}
};
/*
* : https://ei1333.github.io/library/structure/wavelet/wavelet-matrix.cpp.html
* @brief Wavelet-Matrix()
* @docs docs/wavelet-matrix.md
*/
template< typename T, int MAXLOG >
struct WaveletMatrix {
size_t length;
SuccinctIndexableDictionary matrix[MAXLOG];
int mid[MAXLOG];
WaveletMatrix() = default;
WaveletMatrix(vector< T > v) : length(v.size()) {
vector< T > l(length), r(length);
for (int level = MAXLOG - 1; level >= 0; level--) {
matrix[level] = SuccinctIndexableDictionary(length + 1);
int left = 0, right = 0;
for (int i = 0; i < length; i++) {
if (((v[i] >> level) & 1)) {
matrix[level].set(i);
r[right++] = v[i];
}
else {
l[left++] = v[i];
}
}
mid[level] = left;
matrix[level].build();
v.swap(l);
for (int i = 0; i < right; i++) {
v[left + i] = r[i];
}
}
}
pair< int, int > succ(bool f, int l, int r, int level) {
return { matrix[level].rank(f, l) + mid[level] * f, matrix[level].rank(f, r) + mid[level] * f };
}
// v[k]
T access(int k) {
T ret = 0;
for (int level = MAXLOG - 1; level >= 0; level--) {
bool f = matrix[level][k];
if (f) ret |= T(1) << level;
k = matrix[level].rank(f, k) + mid[level] * f;
}
return ret;
}
T operator[](const int &k) {
return access(k);
}
// count i s.t. (0 <= i < r) && v[i] == x
int rank(const T &x, int r) {
int l = 0;
for (int level = MAXLOG - 1; level >= 0; level--) {
tie(l, r) = succ((x >> level) & 1, l, r, level);
}
return r - l;
}
// k-th(0-indexed) smallest number in v[l,r)
T kth_smallest(int l, int r, int k) {
assert(0 <= k && k < r - l);
T ret = 0;
for (int level = MAXLOG - 1; level >= 0; level--) {
int cnt = matrix[level].rank(false, r) - matrix[level].rank(false, l);
bool f = cnt <= k;
if (f) {
ret |= T(1) << level;
k -= cnt;
}
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// k-th(0-indexed) largest number in v[l,r)
T kth_largest(int l, int r, int k) {
return kth_smallest(l, r, r - l - k - 1);
}
// count i s.t. (l <= i < r) && (v[i] < upper)
int range_freq(int l, int r, T upper) {
int ret = 0;
for (int level = MAXLOG - 1; level >= 0; level--) {
bool f = ((upper >> level) & 1);
if (f) ret += matrix[level].rank(false, r) - matrix[level].rank(false, l);
tie(l, r) = succ(f, l, r, level);
}
return ret;
}
// count i s.t. (l <= i < r) && (lower <= v[i] < upper)
int range_freq(int l, int r, T lower, T upper) {
return range_freq(l, r, upper) - range_freq(l, r, lower);
}
// max v[i] s.t. (l <= i < r) && (v[i] < upper)
T prev_value(int l, int r, T upper) {
int cnt = range_freq(l, r, upper);
return cnt == 0 ? T(-1) : kth_smallest(l, r, cnt - 1);
}
// min v[i] s.t. (l <= i < r) && (lower <= v[i])
T next_value(int l, int r, T lower) {
int cnt = range_freq(l, r, lower);
return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
}
};
/*
: https://ei1333.github.io/library/structure/wavelet/wavelet-matrix.cpp.html
*/
template< typename T, int MAXLOG >
struct CompressedWaveletMatrix {
WaveletMatrix< int, MAXLOG > mat;
vector< T > ys;
CompressedWaveletMatrix(const vector< T > &v) : ys(v) {
sort(begin(ys), end(ys));
ys.erase(unique(begin(ys), end(ys)), end(ys));
vector< int > t(v.size());
for (int i = 0; i < v.size(); i++) t[i] = get(v[i]);
mat = WaveletMatrix< int, MAXLOG >(t);
}
inline int get(const T& x) {
return lower_bound(begin(ys), end(ys), x) - begin(ys);
}
T access(int k) {
return ys[mat.access(k)];
}
T operator[](const int &k) {
return access(k);
}
int rank(const T &x, int r) {
auto pos = get(x);
if (pos == ys.size() || ys[pos] != x) return 0;
return mat.rank(pos, r);
}
T kth_smallest(int l, int r, int k) {
return ys[mat.kth_smallest(l, r, k)];
}
T kth_largest(int l, int r, int k) {
return ys[mat.kth_largest(l, r, k)];
}
int range_freq(int l, int r, T upper) {
return mat.range_freq(l, r, get(upper));
}
int range_freq(int l, int r, T lower, T upper) {
return mat.range_freq(l, r, get(lower), get(upper));
}
T prev_value(int l, int r, T upper) {
auto ret = mat.prev_value(l, r, get(upper));
return ret == -1 ? T(-1) : ys[ret];
}
T next_value(int l, int r, T lower) {
auto ret = mat.next_value(l, r, get(lower));
return ret == -1 ? T(-1) : ys[ret];
}
};
// [l1, r1), [l2, r2){, {l, r}} [l, r)
pair<bool, pair<int, int>> RangeIntersection(int l1, int r1, int l2, int r2) {
int r = min(r1, r2);
int l = max(l1, l2);
if (r - l <= 0) {
return{ false, {-1, -1} };
}
else {
return { true, {l, r} };
}
}
// ACL
#ifdef ACL_ENABLED
template<typename T>
shared_ptr<atcoder::fenwick_tree<T>> create_fenwick(vector<T> const& v) {
int vlen = v.size();
shared_ptr<atcoder::fenwick_tree<T>> ret = make_shared<atcoder::fenwick_tree<T>>(vlen);
rep(i, vlen) {
ret->add(i, v[i]);
}
return ret;
}
#endif // ACL_ENABLED
// Boost
#ifdef BOOST_ENABLED
// u, v (rad)
double GetAngle(const Vector3D& u, const Vector3D& v)
{
double mag = qvm::mag(u);
double costheta = qvm::dot(u, v) / (qvm::mag(u) * qvm::mag(v));
double ret = acosl(costheta);
return ret;
};
// rad z(≒2D)
Matrix3x3 GetRotateMatrix(double rad, Vector3D axis = Vector3D{0, 0, 1}) {
auto const rotQuat = qvm::rot_quat(axis, rad);
// ->
auto const mat = qvm::convert_to<Matrix3x3>(rotQuat);
return mat;
}
//
#define VECTOR3D_X(v) qvm::X(v)
#define VECTOR3D_Y(v) qvm::Y(v)
#define VECTOR3D_Z(v) qvm::Z(v)
#endif
//
double Rad2Deg(double rad) {
return 180.0L / PI * rad;
}
double Deg2Rad(double deg) {
return deg * PI / 180.0L;
}
void solve(ostringstream& aout, long long A, long long B);
void solve_TLE(ostringstream& aout, long long A, long long B);
class StressTest {
private:
mt19937 m_RandEngine;
bool judge_case(long long A, long long B) {
ostringstream fast, tle;
solve(fast, A, B);
solve_TLE(tle, A, B);
if (fast.str() == tle.str()) {
return true;
}
else {
return false;
}
}
// [l, l+1, ... r]
vector<int> create_range_permutation(int l, int r) {
vector<int> ret;
for (int i = l; i <= r; i++) {
ret.push_back(i);
}
shuffle(ret.begin(), ret.end(), m_RandEngine);
return ret;
}
// [1, n]
vector<int> create_permutation(int n) {
create_range_permutation(1, n);
}
// [l, r] n
vector<int> create_random_sequence(int l, int r, int n) {
uniform_int_distribution<> randLR(l, r);
vector<int> ret;
for (int i = 0; i < n; i++) {
ret.push_back(randLR(m_RandEngine));
}
return ret;
}
/*
* n, m
* 1-indexed AtCoder 1-n 使 n+1 0
* weighted true maxWeight
*
*/
Graph create_undirected_graph(int n, int m, bool weighted = false, int maxWeight = 10) {
Graph ret(n + 1);
set<pair<int, int>> used;
uniform_int_distribution<> randNode(1, n);
uniform_int_distribution<> randWeight(1, maxWeight);
while (used.size() < m * 2) {
int src = randNode(m_RandEngine);
int dst = randNode(m_RandEngine);
//
if (used.count(make_pair(src, dst)) == 0 && used.count(make_pair(dst, src)) == 0 && src != dst) {
used.insert(make_pair(src, dst));
used.insert(make_pair(dst, src));
add_edge(ret, src, dst, weighted ? randWeight(m_RandEngine) : 1);
}
}
return ret;
}
/*
* n, m
* 1-indexed AtCoder 1-n 使 n+1 0
* weighted true maxWeight
*
*/
Graph create_directed_graph(int n, int m, bool weighted = false, int maxWeight = 10) {
Graph ret(n + 1);
set<pair<int, int>> used;
uniform_int_distribution<> randNode(1, n);
uniform_int_distribution<> randWeight(1, maxWeight);
while (used.size() < m) {
int src = randNode(m_RandEngine);
int dst = randNode(m_RandEngine);
//
if (used.count(make_pair(src, dst)) == 0 && src != dst) {
used.insert(make_pair(src, dst));
add_arc(ret, src, dst, weighted ? randWeight(m_RandEngine) : 1);
}
}
return ret;
}
/*
* n()
*/
Graph create_tree(int n, bool weighted = false, int maxWeight = 10) {
Graph ret(n + 1);
uf_tree uf(n + 1);
int cnt = 0;
uniform_int_distribution<> randNode(1, n);
uniform_int_distribution<> randWeight(1, maxWeight);
while (cnt < n - 1) {
int n1 = randNode(m_RandEngine);
int n2 = randNode(m_RandEngine);
if (n1 != n2 && !uf.is_same(n1, n2)) {
cnt++;
add_edge(ret, n1, n2, weighted ? randWeight(m_RandEngine) : 1);
}
}
}
public:
StressTest(int seed) :
m_RandEngine(seed) {}
void test() {
while (1) {
// TODO: generate random case
//if (!judge_case(A, B)) {
// TODO: output case
//break;
//}
}
}
};
void solve(ostringstream& aout, long long A, long long B){
}
void solve_TLE(ostringstream& aout, long long A, long long B) {
}
signed main() {
int N, Q;
cin >> N >> Q;
Graph G(N + 1);
rep(i, N - 1) {
int a, b;
cin >> a >> b;
add_edge(G, a, b);
}
vector<int> p(Q), x(Q);
rep(i, Q) {
cin >> p[i] >> x[i];
}
vector<bool> visited(N + 1, false);
vector<int> subSize(N + 1, 0);
function<int(int)> dfs = [&](int n) -> int {
if (visited[n]) {
return 0;
}
visited[n] = true;
int size = 0;
for (auto e : G[n]) {
size += dfs(e.dst);
}
return subSize[n] = size + 1;
};
dfs(1);
int ans = 0;
rep(i, Q) {
ans += subSize[p[i]] * x[i];
cout << ans << "\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0