QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#711588 | #8570. Idola-Tree | maspy | WA | 2188ms | 75752kb | C++23 | 55.4kb | 2024-11-05 12:21:17 | 2024-11-05 12:21:18 |
Judging History
answer
#line 1 "/home/maspy/compro/library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
// https://codeforces.com/blog/entry/96344
#pragma GCC optimize("Ofast,unroll-loops")
// いまの CF だとこれ入れると動かない?
// #pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;
using f128 = __float128;
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'010'000'000;
template <>
constexpr ll infty<ll> = 2'020'000'000'000'000'000;
template <>
constexpr u32 infty<u32> = infty<int>;
template <>
constexpr u64 infty<u64> = infty<ll>;
template <>
constexpr i128 infty<i128> = i128(infty<ll>) * 2'000'000'000'000'000'000;
template <>
constexpr double infty<double> = infty<ll>;
template <>
constexpr long double infty<long double> = infty<ll>;
using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vv(type, name, h, ...) vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define stoi stoll
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_mod_2(int x) { return __builtin_parity(x); }
int popcnt_mod_2(u32 x) { return __builtin_parity(x); }
int popcnt_mod_2(ll x) { return __builtin_parityll(x); }
int popcnt_mod_2(u64 x) { return __builtin_parityll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
template <typename T>
T floor(T a, T b) {
return a / b - (a % b && (a ^ b) < 0);
}
template <typename T>
T ceil(T x, T y) {
return floor(x + y - 1, y);
}
template <typename T>
T bmod(T x, T y) {
return x - y * floor(x, y);
}
template <typename T>
pair<T, T> divmod(T x, T y) {
T q = floor(x, y);
return {q, x - q * y};
}
template <typename T, typename U>
T SUM(const vector<U> &A) {
T sm = 0;
for (auto &&a: A) sm += a;
return sm;
}
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()
template <typename T>
T POP(deque<T> &que) {
T a = que.front();
que.pop_front();
return a;
}
template <typename T>
T POP(pq<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(pqg<T> &que) {
T a = que.top();
que.pop();
return a;
}
template <typename T>
T POP(vc<T> &que) {
T a = que.back();
que.pop_back();
return a;
}
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
FOR(iter) {
double x = (ok + ng) / 2;
(check(x) ? ok : ng) = x;
}
return (ok + ng) / 2;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
vc<int> A(S.size());
FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
return A;
}
template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
int N = A.size();
vector<T> B(N + 1);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
if (off == 0) B.erase(B.begin());
return B;
}
// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
vector<int> ids(len(A));
iota(all(ids), 0);
sort(all(ids), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
return ids;
}
// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
vc<T> B(len(I));
FOR(i, len(I)) B[i] = A[I[i]];
return B;
}
template <typename T, typename... Vectors>
void concat(vc<T> &first, const Vectors &... others) {
vc<T> &res = first;
(res.insert(res.end(), others.begin(), others.end()), ...);
}
#endif
#line 1 "/home/maspy/compro/library/other/io.hpp"
#define FASTIO
#include <unistd.h>
// https://judge.yosupo.jp/submission/21623
namespace fastio {
static constexpr uint32_t SZ = 1 << 17;
char ibuf[SZ];
char obuf[SZ];
char out[100];
// pointer of ibuf, obuf
uint32_t pil = 0, pir = 0, por = 0;
struct Pre {
char num[10000][4];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i][j] = n % 10 | '0';
n /= 10;
}
}
}
} constexpr pre;
inline void load() {
memcpy(ibuf, ibuf + pil, pir - pil);
pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
pil = 0;
if (pir < SZ) ibuf[pir++] = '\n';
}
inline void flush() {
fwrite(obuf, 1, por, stdout);
por = 0;
}
void rd(char &c) {
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
}
void rd(string &x) {
x.clear();
char c;
do {
if (pil + 1 > pir) load();
c = ibuf[pil++];
} while (isspace(c));
do {
x += c;
if (pil == pir) load();
c = ibuf[pil++];
} while (!isspace(c));
}
template <typename T>
void rd_real(T &x) {
string s;
rd(s);
x = stod(s);
}
template <typename T>
void rd_integer(T &x) {
if (pil + 100 > pir) load();
char c;
do
c = ibuf[pil++];
while (c < '-');
bool minus = 0;
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (c == '-') { minus = 1, c = ibuf[pil++]; }
}
x = 0;
while ('0' <= c) { x = x * 10 + (c & 15), c = ibuf[pil++]; }
if constexpr (is_signed<T>::value || is_same_v<T, i128>) {
if (minus) x = -x;
}
}
void rd(int &x) { rd_integer(x); }
void rd(ll &x) { rd_integer(x); }
void rd(i128 &x) { rd_integer(x); }
void rd(u32 &x) { rd_integer(x); }
void rd(u64 &x) { rd_integer(x); }
void rd(u128 &x) { rd_integer(x); }
void rd(double &x) { rd_real(x); }
void rd(long double &x) { rd_real(x); }
void rd(f128 &x) { rd_real(x); }
template <class T, class U>
void rd(pair<T, U> &p) {
return rd(p.first), rd(p.second);
}
template <size_t N = 0, typename T>
void rd_tuple(T &t) {
if constexpr (N < std::tuple_size<T>::value) {
auto &x = std::get<N>(t);
rd(x);
rd_tuple<N + 1>(t);
}
}
template <class... T>
void rd(tuple<T...> &tpl) {
rd_tuple(tpl);
}
template <size_t N = 0, typename T>
void rd(array<T, N> &x) {
for (auto &d: x) rd(d);
}
template <class T>
void rd(vc<T> &x) {
for (auto &d: x) rd(d);
}
void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
rd(h), read(t...);
}
void wt(const char c) {
if (por == SZ) flush();
obuf[por++] = c;
}
void wt(const string s) {
for (char c: s) wt(c);
}
void wt(const char *s) {
size_t len = strlen(s);
for (size_t i = 0; i < len; i++) wt(s[i]);
}
template <typename T>
void wt_integer(T x) {
if (por > SZ - 100) flush();
if (x < 0) { obuf[por++] = '-', x = -x; }
int outi;
for (outi = 96; x >= 10000; outi -= 4) {
memcpy(out + outi, pre.num[x % 10000], 4);
x /= 10000;
}
if (x >= 1000) {
memcpy(obuf + por, pre.num[x], 4);
por += 4;
} else if (x >= 100) {
memcpy(obuf + por, pre.num[x] + 1, 3);
por += 3;
} else if (x >= 10) {
int q = (x * 103) >> 10;
obuf[por] = q | '0';
obuf[por + 1] = (x - q * 10) | '0';
por += 2;
} else
obuf[por++] = x | '0';
memcpy(obuf + por, out + outi + 4, 96 - outi);
por += 96 - outi;
}
template <typename T>
void wt_real(T x) {
ostringstream oss;
oss << fixed << setprecision(15) << double(x);
string s = oss.str();
wt(s);
}
void wt(int x) { wt_integer(x); }
void wt(ll x) { wt_integer(x); }
void wt(i128 x) { wt_integer(x); }
void wt(u32 x) { wt_integer(x); }
void wt(u64 x) { wt_integer(x); }
void wt(u128 x) { wt_integer(x); }
void wt(double x) { wt_real(x); }
void wt(long double x) { wt_real(x); }
void wt(f128 x) { wt_real(x); }
template <class T, class U>
void wt(const pair<T, U> val) {
wt(val.first);
wt(' ');
wt(val.second);
}
template <size_t N = 0, typename T>
void wt_tuple(const T t) {
if constexpr (N < std::tuple_size<T>::value) {
if constexpr (N > 0) { wt(' '); }
const auto x = std::get<N>(t);
wt(x);
wt_tuple<N + 1>(t);
}
}
template <class... T>
void wt(tuple<T...> tpl) {
wt_tuple(tpl);
}
template <class T, size_t S>
void wt(const array<T, S> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
template <class T>
void wt(const vector<T> val) {
auto n = val.size();
for (size_t i = 0; i < n; i++) {
if (i) wt(' ');
wt(val[i]);
}
}
void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
wt(head);
if (sizeof...(Tail)) wt(' ');
print(forward<Tail>(tail)...);
}
// gcc expansion. called automaticall after main.
void __attribute__((destructor)) _d() { flush(); }
} // namespace fastio
using fastio::read;
using fastio::print;
using fastio::flush;
#if defined(LOCAL)
#define SHOW(...) SHOW_IMPL(__VA_ARGS__, SHOW6, SHOW5, SHOW4, SHOW3, SHOW2, SHOW1)(__VA_ARGS__)
#define SHOW_IMPL(_1, _2, _3, _4, _5, _6, NAME, ...) NAME
#define SHOW1(x) print(#x, "=", (x)), flush()
#define SHOW2(x, y) print(#x, "=", (x), #y, "=", (y)), flush()
#define SHOW3(x, y, z) print(#x, "=", (x), #y, "=", (y), #z, "=", (z)), flush()
#define SHOW4(x, y, z, w) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w)), flush()
#define SHOW5(x, y, z, w, v) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v)), flush()
#define SHOW6(x, y, z, w, v, u) print(#x, "=", (x), #y, "=", (y), #z, "=", (z), #w, "=", (w), #v, "=", (v), #u, "=", (u)), flush()
#else
#define SHOW(...)
#endif
#define INT(...) \
int __VA_ARGS__; \
read(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
read(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
read(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
read(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
read(__VA_ARGS__)
#define CHAR(...) \
char __VA_ARGS__; \
read(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
read(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
read(name)
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
read(name)
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 3 "main.cpp"
#line 2 "/home/maspy/compro/library/graph/base.hpp"
template <typename T>
struct Edge {
int frm, to;
T cost;
int id;
};
template <typename T = int, bool directed = false>
struct Graph {
static constexpr bool is_directed = directed;
int N, M;
using cost_type = T;
using edge_type = Edge<T>;
vector<edge_type> edges;
vector<int> indptr;
vector<edge_type> csr_edges;
vc<int> vc_deg, vc_indeg, vc_outdeg;
bool prepared;
class OutgoingEdges {
public:
OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}
const edge_type* begin() const {
if (l == r) { return 0; }
return &G->csr_edges[l];
}
const edge_type* end() const {
if (l == r) { return 0; }
return &G->csr_edges[r];
}
private:
const Graph* G;
int l, r;
};
bool is_prepared() { return prepared; }
Graph() : N(0), M(0), prepared(0) {}
Graph(int N) : N(N), M(0), prepared(0) {}
void build(int n) {
N = n, M = 0;
prepared = 0;
edges.clear();
indptr.clear();
csr_edges.clear();
vc_deg.clear();
vc_indeg.clear();
vc_outdeg.clear();
}
void add(int frm, int to, T cost = 1, int i = -1) {
assert(!prepared);
assert(0 <= frm && 0 <= to && to < N);
if (i == -1) i = M;
auto e = edge_type({frm, to, cost, i});
edges.eb(e);
++M;
}
#ifdef FASTIO
// wt, off
void read_tree(bool wt = false, int off = 1) { read_graph(N - 1, wt, off); }
void read_graph(int M, bool wt = false, int off = 1) {
for (int m = 0; m < M; ++m) {
INT(a, b);
a -= off, b -= off;
if (!wt) {
add(a, b);
} else {
T c;
read(c);
add(a, b, c);
}
}
build();
}
#endif
void build() {
assert(!prepared);
prepared = true;
indptr.assign(N + 1, 0);
for (auto&& e: edges) {
indptr[e.frm + 1]++;
if (!directed) indptr[e.to + 1]++;
}
for (int v = 0; v < N; ++v) { indptr[v + 1] += indptr[v]; }
auto counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (auto&& e: edges) {
csr_edges[counter[e.frm]++] = e;
if (!directed)
csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
}
}
OutgoingEdges operator[](int v) const {
assert(prepared);
return {this, indptr[v], indptr[v + 1]};
}
vc<int> deg_array() {
if (vc_deg.empty()) calc_deg();
return vc_deg;
}
pair<vc<int>, vc<int>> deg_array_inout() {
if (vc_indeg.empty()) calc_deg_inout();
return {vc_indeg, vc_outdeg};
}
int deg(int v) {
if (vc_deg.empty()) calc_deg();
return vc_deg[v];
}
int in_deg(int v) {
if (vc_indeg.empty()) calc_deg_inout();
return vc_indeg[v];
}
int out_deg(int v) {
if (vc_outdeg.empty()) calc_deg_inout();
return vc_outdeg[v];
}
#ifdef FASTIO
void debug() {
print("Graph");
if (!prepared) {
print("frm to cost id");
for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id);
} else {
print("indptr", indptr);
print("frm to cost id");
FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id);
}
}
#endif
vc<int> new_idx;
vc<bool> used_e;
// G における頂点 V[i] が、新しいグラフで i になるようにする
// {G, es}
// sum(deg(v)) の計算量になっていて、
// 新しいグラフの n+m より大きい可能性があるので注意
Graph<T, directed> rearrange(vc<int> V, bool keep_eid = 0) {
if (len(new_idx) != N) new_idx.assign(N, -1);
int n = len(V);
FOR(i, n) new_idx[V[i]] = i;
Graph<T, directed> G(n);
vc<int> history;
FOR(i, n) {
for (auto&& e: (*this)[V[i]]) {
if (len(used_e) <= e.id) used_e.resize(e.id + 1);
if (used_e[e.id]) continue;
int a = e.frm, b = e.to;
if (new_idx[a] != -1 && new_idx[b] != -1) {
history.eb(e.id);
used_e[e.id] = 1;
int eid = (keep_eid ? e.id : -1);
G.add(new_idx[a], new_idx[b], e.cost, eid);
}
}
}
FOR(i, n) new_idx[V[i]] = -1;
for (auto&& eid: history) used_e[eid] = 0;
G.build();
return G;
}
Graph<T, true> to_directed_tree(int root = -1) {
if (root == -1) root = 0;
assert(!is_directed && prepared && M == N - 1);
Graph<T, true> G1(N);
vc<int> par(N, -1);
auto dfs = [&](auto& dfs, int v) -> void {
for (auto& e: (*this)[v]) {
if (e.to == par[v]) continue;
par[e.to] = v, dfs(dfs, e.to);
}
};
dfs(dfs, root);
for (auto& e: edges) {
int a = e.frm, b = e.to;
if (par[a] == b) swap(a, b);
assert(par[b] == a);
G1.add(a, b, e.cost);
}
G1.build();
return G1;
}
private:
void calc_deg() {
assert(vc_deg.empty());
vc_deg.resize(N);
for (auto&& e: edges) vc_deg[e.frm]++, vc_deg[e.to]++;
}
void calc_deg_inout() {
assert(vc_indeg.empty());
vc_indeg.resize(N);
vc_outdeg.resize(N);
for (auto&& e: edges) { vc_indeg[e.to]++, vc_outdeg[e.frm]++; }
}
};
#line 2 "/home/maspy/compro/library/mod/modint_common.hpp"
struct has_mod_impl {
template <class T>
static auto check(T &&x) -> decltype(x.get_mod(), std::true_type{});
template <class T>
static auto check(...) -> std::false_type;
};
template <class T>
class has_mod : public decltype(has_mod_impl::check<T>(std::declval<T>())) {};
template <typename mint>
mint inv(int n) {
static const int mod = mint::get_mod();
static vector<mint> dat = {0, 1};
assert(0 <= n);
if (n >= mod) n %= mod;
while (len(dat) <= n) {
int k = len(dat);
int q = (mod + k - 1) / k;
dat.eb(dat[k * q - mod] * mint::raw(q));
}
return dat[n];
}
template <typename mint>
mint fact(int n) {
static const int mod = mint::get_mod();
assert(0 <= n && n < mod);
static vector<mint> dat = {1, 1};
while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * mint::raw(len(dat)));
return dat[n];
}
template <typename mint>
mint fact_inv(int n) {
static vector<mint> dat = {1, 1};
if (n < 0) return mint(0);
while (len(dat) <= n) dat.eb(dat[len(dat) - 1] * inv<mint>(len(dat)));
return dat[n];
}
template <class mint, class... Ts>
mint fact_invs(Ts... xs) {
return (mint(1) * ... * fact_inv<mint>(xs));
}
template <typename mint, class Head, class... Tail>
mint multinomial(Head &&head, Tail &&... tail) {
return fact<mint>(head) * fact_invs<mint>(std::forward<Tail>(tail)...);
}
template <typename mint>
mint C_dense(int n, int k) {
static vvc<mint> C;
static int H = 0, W = 0;
auto calc = [&](int i, int j) -> mint {
if (i == 0) return (j == 0 ? mint(1) : mint(0));
return C[i - 1][j] + (j ? C[i - 1][j - 1] : 0);
};
if (W <= k) {
FOR(i, H) {
C[i].resize(k + 1);
FOR(j, W, k + 1) { C[i][j] = calc(i, j); }
}
W = k + 1;
}
if (H <= n) {
C.resize(n + 1);
FOR(i, H, n + 1) {
C[i].resize(W);
FOR(j, W) { C[i][j] = calc(i, j); }
}
H = n + 1;
}
return C[n][k];
}
template <typename mint, bool large = false, bool dense = false>
mint C(ll n, ll k) {
assert(n >= 0);
if (k < 0 || n < k) return 0;
if constexpr (dense) return C_dense<mint>(n, k);
if constexpr (!large) return multinomial<mint>(n, k, n - k);
k = min(k, n - k);
mint x(1);
FOR(i, k) x *= mint(n - i);
return x * fact_inv<mint>(k);
}
template <typename mint, bool large = false>
mint C_inv(ll n, ll k) {
assert(n >= 0);
assert(0 <= k && k <= n);
if (!large) return fact_inv<mint>(n) * fact<mint>(k) * fact<mint>(n - k);
return mint(1) / C<mint, 1>(n, k);
}
// [x^d](1-x)^{-n}
template <typename mint, bool large = false, bool dense = false>
mint C_negative(ll n, ll d) {
assert(n >= 0);
if (d < 0) return mint(0);
if (n == 0) { return (d == 0 ? mint(1) : mint(0)); }
return C<mint, large, dense>(n + d - 1, d);
}
#line 3 "/home/maspy/compro/library/mod/modint.hpp"
template <int mod>
struct modint {
static constexpr u32 umod = u32(mod);
static_assert(umod < u32(1) << 31);
u32 val;
static modint raw(u32 v) {
modint x;
x.val = v;
return x;
}
constexpr modint() : val(0) {}
constexpr modint(u32 x) : val(x % umod) {}
constexpr modint(u64 x) : val(x % umod) {}
constexpr modint(u128 x) : val(x % umod) {}
constexpr modint(int x) : val((x %= mod) < 0 ? x + mod : x){};
constexpr modint(ll x) : val((x %= mod) < 0 ? x + mod : x){};
constexpr modint(i128 x) : val((x %= mod) < 0 ? x + mod : x){};
bool operator<(const modint &other) const { return val < other.val; }
modint &operator+=(const modint &p) {
if ((val += p.val) >= umod) val -= umod;
return *this;
}
modint &operator-=(const modint &p) {
if ((val += umod - p.val) >= umod) val -= umod;
return *this;
}
modint &operator*=(const modint &p) {
val = u64(val) * p.val % umod;
return *this;
}
modint &operator/=(const modint &p) {
*this *= p.inverse();
return *this;
}
modint operator-() const { return modint::raw(val ? mod - val : u32(0)); }
modint operator+(const modint &p) const { return modint(*this) += p; }
modint operator-(const modint &p) const { return modint(*this) -= p; }
modint operator*(const modint &p) const { return modint(*this) *= p; }
modint operator/(const modint &p) const { return modint(*this) /= p; }
bool operator==(const modint &p) const { return val == p.val; }
bool operator!=(const modint &p) const { return val != p.val; }
modint inverse() const {
int a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
return modint(u);
}
modint pow(ll n) const {
assert(n >= 0);
modint ret(1), mul(val);
while (n > 0) {
if (n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
static constexpr int get_mod() { return mod; }
// (n, r), r は 1 の 2^n 乗根
static constexpr pair<int, int> ntt_info() {
if (mod == 120586241) return {20, 74066978};
if (mod == 167772161) return {25, 17};
if (mod == 469762049) return {26, 30};
if (mod == 754974721) return {24, 362};
if (mod == 880803841) return {23, 211};
if (mod == 943718401) return {22, 663003469};
if (mod == 998244353) return {23, 31};
if (mod == 1004535809) return {21, 582313106};
if (mod == 1012924417) return {21, 368093570};
return {-1, -1};
}
static constexpr bool can_ntt() { return ntt_info().fi != -1; }
};
#ifdef FASTIO
template <int mod>
void rd(modint<mod> &x) {
fastio::rd(x.val);
x.val %= mod;
// assert(0 <= x.val && x.val < mod);
}
template <int mod>
void wt(modint<mod> x) {
fastio::wt(x.val);
}
#endif
using modint107 = modint<1000000007>;
using modint998 = modint<998244353>;
#line 2 "/home/maspy/compro/library/graph/tree.hpp"
#line 4 "/home/maspy/compro/library/graph/tree.hpp"
// HLD euler tour をとっていろいろ。
template <typename GT>
struct Tree {
using Graph_type = GT;
GT &G;
using WT = typename GT::cost_type;
int N;
vector<int> LID, RID, head, V, parent, VtoE;
vc<int> depth;
vc<WT> depth_weighted;
Tree(GT &G, int r = 0, bool hld = 1) : G(G) { build(r, hld); }
void build(int r = 0, bool hld = 1) {
if (r == -1) return; // build を遅延したいとき
N = G.N;
LID.assign(N, -1), RID.assign(N, -1), head.assign(N, r);
V.assign(N, -1), parent.assign(N, -1), VtoE.assign(N, -1);
depth.assign(N, -1), depth_weighted.assign(N, 0);
assert(G.is_prepared());
int t1 = 0;
dfs_sz(r, -1, hld);
dfs_hld(r, t1);
}
void dfs_sz(int v, int p, bool hld) {
auto &sz = RID;
parent[v] = p;
depth[v] = (p == -1 ? 0 : depth[p] + 1);
sz[v] = 1;
int l = G.indptr[v], r = G.indptr[v + 1];
auto &csr = G.csr_edges;
// 使う辺があれば先頭にする
for (int i = r - 2; i >= l; --i) {
if (hld && depth[csr[i + 1].to] == -1) swap(csr[i], csr[i + 1]);
}
int hld_sz = 0;
for (int i = l; i < r; ++i) {
auto e = csr[i];
if (depth[e.to] != -1) continue;
depth_weighted[e.to] = depth_weighted[v] + e.cost;
VtoE[e.to] = e.id;
dfs_sz(e.to, v, hld);
sz[v] += sz[e.to];
if (hld && chmax(hld_sz, sz[e.to]) && l < i) { swap(csr[l], csr[i]); }
}
}
void dfs_hld(int v, int ×) {
LID[v] = times++;
RID[v] += LID[v];
V[LID[v]] = v;
bool heavy = true;
for (auto &&e: G[v]) {
if (depth[e.to] <= depth[v]) continue;
head[e.to] = (heavy ? head[v] : e.to);
heavy = false;
dfs_hld(e.to, times);
}
}
vc<int> heavy_path_at(int v) {
vc<int> P = {v};
while (1) {
int a = P.back();
for (auto &&e: G[a]) {
if (e.to != parent[a] && head[e.to] == v) {
P.eb(e.to);
break;
}
}
if (P.back() == a) break;
}
return P;
}
int heavy_child(int v) {
int k = LID[v] + 1;
if (k == N) return -1;
int w = V[k];
return (parent[w] == v ? w : -1);
}
int e_to_v(int eid) {
auto e = G.edges[eid];
return (parent[e.frm] == e.to ? e.frm : e.to);
}
int v_to_e(int v) { return VtoE[v]; }
int get_eid(int u, int v) {
if (parent[u] != v) swap(u, v);
assert(parent[u] == v);
return VtoE[u];
}
int ELID(int v) { return 2 * LID[v] - depth[v]; }
int ERID(int v) { return 2 * RID[v] - depth[v] - 1; }
// 目標地点へ進む個数が k
int LA(int v, int k) {
assert(k <= depth[v]);
while (1) {
int u = head[v];
if (LID[v] - k >= LID[u]) return V[LID[v] - k];
k -= LID[v] - LID[u] + 1;
v = parent[u];
}
}
int la(int u, int v) { return LA(u, v); }
int LCA(int u, int v) {
for (;; v = parent[head[v]]) {
if (LID[u] > LID[v]) swap(u, v);
if (head[u] == head[v]) return u;
}
}
int meet(int a, int b, int c) { return LCA(a, b) ^ LCA(a, c) ^ LCA(b, c); }
int lca(int u, int v) { return LCA(u, v); }
int subtree_size(int v, int root = -1) {
if (root == -1) return RID[v] - LID[v];
if (v == root) return N;
int x = jump(v, root, 1);
if (in_subtree(v, x)) return RID[v] - LID[v];
return N - RID[x] + LID[x];
}
int dist(int a, int b) {
int c = LCA(a, b);
return depth[a] + depth[b] - 2 * depth[c];
}
WT dist_weighted(int a, int b) {
int c = LCA(a, b);
return depth_weighted[a] + depth_weighted[b] - WT(2) * depth_weighted[c];
}
// a is in b
bool in_subtree(int a, int b) { return LID[b] <= LID[a] && LID[a] < RID[b]; }
int jump(int a, int b, ll k) {
if (k == 1) {
if (a == b) return -1;
return (in_subtree(b, a) ? LA(b, depth[b] - depth[a] - 1) : parent[a]);
}
int c = LCA(a, b);
int d_ac = depth[a] - depth[c];
int d_bc = depth[b] - depth[c];
if (k > d_ac + d_bc) return -1;
if (k <= d_ac) return LA(a, k);
return LA(b, d_ac + d_bc - k);
}
vc<int> collect_child(int v) {
vc<int> res;
for (auto &&e: G[v])
if (e.to != parent[v]) res.eb(e.to);
return res;
}
vc<int> collect_light(int v) {
vc<int> res;
bool skip = true;
for (auto &&e: G[v])
if (e.to != parent[v]) {
if (!skip) res.eb(e.to);
skip = false;
}
return res;
}
vc<pair<int, int>> get_path_decomposition(int u, int v, bool edge) {
// [始点, 終点] の"閉"区間列。
vc<pair<int, int>> up, down;
while (1) {
if (head[u] == head[v]) break;
if (LID[u] < LID[v]) {
down.eb(LID[head[v]], LID[v]);
v = parent[head[v]];
} else {
up.eb(LID[u], LID[head[u]]);
u = parent[head[u]];
}
}
if (LID[u] < LID[v]) down.eb(LID[u] + edge, LID[v]);
elif (LID[v] + edge <= LID[u]) up.eb(LID[u], LID[v] + edge);
reverse(all(down));
up.insert(up.end(), all(down));
return up;
}
// 辺の列の情報 (frm,to,str)
// str = "heavy_up", "heavy_down", "light_up", "light_down"
vc<tuple<int, int, string>> get_path_decomposition_detail(int u, int v) {
vc<tuple<int, int, string>> up, down;
while (1) {
if (head[u] == head[v]) break;
if (LID[u] < LID[v]) {
if (v != head[v]) down.eb(head[v], v, "heavy_down"), v = head[v];
down.eb(parent[v], v, "light_down"), v = parent[v];
} else {
if (u != head[u]) up.eb(u, head[u], "heavy_up"), u = head[u];
up.eb(u, parent[u], "light_up"), u = parent[u];
}
}
if (LID[u] < LID[v]) down.eb(u, v, "heavy_down");
elif (LID[v] < LID[u]) up.eb(u, v, "heavy_up");
reverse(all(down));
concat(up, down);
return up;
}
vc<int> restore_path(int u, int v) {
vc<int> P;
for (auto &&[a, b]: get_path_decomposition(u, v, 0)) {
if (a <= b) {
FOR(i, a, b + 1) P.eb(V[i]);
} else {
FOR_R(i, b, a + 1) P.eb(V[i]);
}
}
return P;
}
// path [a,b] と [c,d] の交わり. 空ならば {-1,-1}.
// https://codeforces.com/problemset/problem/500/G
pair<int, int> path_intersection(int a, int b, int c, int d) {
int ab = lca(a, b), ac = lca(a, c), ad = lca(a, d);
int bc = lca(b, c), bd = lca(b, d), cd = lca(c, d);
int x = ab ^ ac ^ bc, y = ab ^ ad ^ bd; // meet(a,b,c), meet(a,b,d)
if (x != y) return {x, y};
int z = ac ^ ad ^ cd;
if (x != z) x = -1;
return {x, x};
}
};
#line 4 "/home/maspy/compro/library/graph/tree_dp/rerooting_dp.hpp"
template <typename TREE, typename Data>
struct Rerooting_dp {
static_assert(!TREE::Graph_type::is_directed);
TREE& tree;
vc<Data> dp_1; // 辺 pv に対して、部分木 v
vc<Data> dp_2; // 辺 pv に対して、部分木 p
vc<Data> dp; // full tree
template <typename F1, typename F2, typename F3>
Rerooting_dp(TREE& tree, F1 f_ee, F2 f_ev, F3 f_ve, const Data unit)
: tree(tree) {
build(f_ee, f_ev, f_ve, unit);
}
// v を根としたときの full tree
Data operator[](int v) { return dp[v]; }
// root を根としたときの部分木 v
Data get(int v, int root) {
if (root == v) return dp[v];
if (!tree.in_subtree(root, v)) { return dp_1[v]; }
int w = tree.jump(v, root, 1);
return dp_2[w];
}
template <typename F1, typename F2, typename F3>
void build(F1 f_ee, F2 f_ev, F3 f_ve, const Data unit) {
int N = tree.N;
// dp1: subtree
dp_1.assign(N, unit);
FOR_R(i, N) {
int v = tree.V[i];
for (auto&& e: tree.G[v]) {
if (e.to == tree.parent[v]) continue;
dp_1[v] = f_ee(dp_1[v], f_ve(dp_1[e.to], e));
}
dp_1[v] = f_ev(dp_1[v], v);
}
// dp2[v]: subtree of p, rooted at v
dp_2.assign(N, unit);
// dp[v]: fulltree, rooted at v
dp.assign(N, unit);
FOR(i, N) {
int p = tree.V[i];
vc<int> ch;
vc<Data> ch_data;
Data x = unit;
for (auto&& e: tree.G[p]) {
if (e.to == tree.parent[p]) {
x = f_ve(dp_2[p], e);
} else {
ch.eb(e.to);
ch_data.eb(f_ve(dp_1[e.to], e));
}
}
int n = len(ch);
if (!n) {
dp[p] = f_ev(x, p);
continue;
}
vc<Data> prod_left(n, x);
FOR(i, n - 1) prod_left[i + 1] = f_ee(prod_left[i], ch_data[i]);
Data prod_right = unit;
FOR_R(i, n) {
dp_2[ch[i]] = f_ev(f_ee(prod_left[i], prod_right), p);
prod_right = f_ee(prod_right, ch_data[i]);
}
dp[p] = f_ev(f_ee(x, prod_right), p);
}
}
};
#line 3 "/home/maspy/compro/library/graph/shortest_path/bfs01.hpp"
template <typename T, typename GT>
pair<vc<T>, vc<int>> bfs01(GT& G, int v) {
assert(G.is_prepared());
int N = G.N;
vc<T> dist(N, infty<T>);
vc<int> par(N, -1);
deque<int> que;
dist[v] = 0;
que.push_front(v);
while (!que.empty()) {
auto v = que.front();
que.pop_front();
for (auto&& e: G[v]) {
if (dist[e.to] == infty<T> || dist[e.to] > dist[e.frm] + e.cost) {
dist[e.to] = dist[e.frm] + e.cost;
par[e.to] = e.frm;
if (e.cost == 0)
que.push_front(e.to);
else
que.push_back(e.to);
}
}
}
return {dist, par};
}
// 多点スタート。[dist, par, root]
template <typename T, typename GT>
tuple<vc<T>, vc<int>, vc<int>> bfs01(GT& G, vc<int> vs) {
assert(G.is_prepared());
int N = G.N;
vc<T> dist(N, infty<T>);
vc<int> par(N, -1);
vc<int> root(N, -1);
deque<int> que;
for (auto&& v: vs) {
dist[v] = 0;
root[v] = v;
que.push_front(v);
}
while (!que.empty()) {
auto v = que.front();
que.pop_front();
for (auto&& e: G[v]) {
if (dist[e.to] == infty<T> || dist[e.to] > dist[e.frm] + e.cost) {
dist[e.to] = dist[e.frm] + e.cost;
root[e.to] = root[e.frm];
par[e.to] = e.frm;
if (e.cost == 0)
que.push_front(e.to);
else
que.push_back(e.to);
}
}
}
return {dist, par, root};
}
#line 3 "/home/maspy/compro/library/graph/centroid_decomposition.hpp"
// 頂点ベースの重心分解
// f(par, V, indptr)
template <typename F>
void centroid_decomposition_0_dfs(vc<int>& par, vc<int>& vs, F f) {
const int N = len(par);
assert(N >= 1);
int c = -1;
vc<int> sz(N, 1);
FOR_R(i, N) {
if (sz[i] >= ceil<int>(N, 2)) {
c = i;
break;
}
sz[par[i]] += sz[i];
}
vc<int> color(N);
vc<int> V = {c};
int nc = 1;
FOR(v, 1, N) {
if (par[v] == c) { V.eb(v), color[v] = nc++; }
}
if (c > 0) {
for (int a = par[c]; a != -1; a = par[a]) { color[a] = nc, V.eb(a); }
++nc;
}
FOR(i, N) {
if (i != c && color[i] == 0) color[i] = color[par[i]], V.eb(i);
}
vc<int> indptr(nc + 1);
FOR(i, N) indptr[1 + color[i]]++;
FOR(i, nc) indptr[i + 1] += indptr[i];
vc<int> counter = indptr;
vc<int> ord(N);
for (auto& v: V) { ord[counter[color[v]]++] = v; }
vc<int> new_idx(N);
FOR(i, N) new_idx[ord[i]] = i;
vc<int> name(N);
FOR(i, N) name[new_idx[i]] = vs[i];
{
vc<int> tmp(N, -1);
FOR(i, 1, N) {
int a = new_idx[i], b = new_idx[par[i]];
if (a > b) swap(a, b);
tmp[b] = a;
}
swap(par, tmp);
}
f(par, name, indptr);
FOR(k, 1, nc) {
int L = indptr[k], R = indptr[k + 1];
vc<int> par1(R - L, -1);
vc<int> name1(R - L, -1);
name1[0] = name[0];
FOR(i, L, R) name1[i - L] = name[i];
FOR(i, L, R) { par1[i - L] = max(par[i] - L, -1); }
centroid_decomposition_0_dfs(par1, name1, f);
}
}
/*
https://maspypy.com/%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%83%bb1-3%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%81%ae%e3%81%8a%e7%b5%b5%e6%8f%8f%e3%81%8d
centroid_decomposition_1:長さ 1 以上のパス全体
f(par, V, L1, R1, L2, R2)
[L1, R1): color 1 / [L2, R2): color 2
*/
template <typename F>
void centroid_decomposition_1_dfs(vc<int>& par, vc<int> vs, F f) {
const int N = len(par);
assert(N > 1);
if (N == 2) {
vc<int> p = {-1, 0};
vc<int> v = {vs[0], vs[1]};
f(p, vs, 0, 1, 1, 2);
return;
}
int c = -1;
vc<int> sz(N, 1);
FOR_R(i, N) {
if (sz[i] >= ceil<int>(N, 2)) {
c = i;
break;
}
sz[par[i]] += sz[i];
}
vc<int> color(N, -1);
int take = 0;
vc<int> ord(N, -1);
ord[c] = 0;
int p = 1;
FOR(v, 1, N) {
if (par[v] == c && take + sz[v] <= floor<int>(N - 1, 2)) { color[v] = 0, ord[v] = p++, take += sz[v]; }
}
FOR(i, 1, N) {
if (color[par[i]] == 0) color[i] = 0, ord[i] = p++;
}
int n0 = p - 1;
for (int a = par[c]; a != -1; a = par[a]) { color[a] = 1, ord[a] = p++; }
FOR(i, N) {
if (i != c && color[i] == -1) color[i] = 1, ord[i] = p++;
}
assert(p == N);
int n1 = N - 1 - n0;
vc<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(N, -1);
vc<int> V0(n0 + 1), V1(n1 + 1), V2(N);
FOR(v, N) {
int i = ord[v];
V2[i] = vs[v];
if (color[v] != 1) { V0[i] = vs[v]; }
if (color[v] != 0) { V1[max(i - n0, 0)] = vs[v]; }
}
FOR(v, 1, N) {
int a = ord[v], b = ord[par[v]];
if (a > b) swap(a, b);
par2[b] = a;
if (color[v] != 1 && color[par[v]] != 1) par0[b] = a;
if (color[v] != 0 && color[par[v]] != 0) par1[max(b - n0, 0)] = max(a - n0, 0);
}
f(par2, V2, 1, 1 + n0, 1 + n0, 1 + n0 + n1);
centroid_decomposition_1_dfs(par0, V0, f);
centroid_decomposition_1_dfs(par1, V1, f);
}
/*
https://maspypy.com/%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%83%bb1-3%e9%87%8d%e5%bf%83%e5%88%86%e8%a7%a3%e3%81%ae%e3%81%8a%e7%b5%b5%e6%8f%8f%e3%81%8d
f(par, V, color)
color in [-1,0,1], -1 is virtual.
*/
template <typename F>
void centroid_decomposition_2_dfs(vc<int>& par, vc<int>& vs, vc<int>& real, F f) {
const int N = len(par);
assert(N > 1);
if (N == 2) {
if (real[0] && real[1]) {
vc<int> color = {0, 1};
f(par, vs, color);
}
return;
}
int c = -1;
vc<int> sz(N, 1);
FOR_R(i, N) {
if (sz[i] >= ceil<int>(N, 2)) {
c = i;
break;
}
sz[par[i]] += sz[i];
}
vc<int> color(N, -1);
int take = 0;
vc<int> ord(N, -1);
ord[c] = 0;
int p = 1;
FOR(v, 1, N) {
if (par[v] == c && take + sz[v] <= floor<int>(N - 1, 2)) { color[v] = 0, ord[v] = p++, take += sz[v]; }
}
FOR(i, 1, N) {
if (color[par[i]] == 0) color[i] = 0, ord[i] = p++;
}
int n0 = p - 1;
for (int a = par[c]; a != -1; a = par[a]) { color[a] = 1, ord[a] = p++; }
FOR(i, N) {
if (i != c && color[i] == -1) color[i] = 1, ord[i] = p++;
}
assert(p == N);
int n1 = N - 1 - n0;
vc<int> par0(n0 + 1, -1), par1(n1 + 1, -1), par2(N, -1);
vc<int> V0(n0 + 1), V1(n1 + 1), V2(N);
vc<int> rea0(n0 + 1), rea1(n1 + 1), rea2(N);
FOR(v, N) {
int i = ord[v];
V2[i] = vs[v], rea2[i] = real[v];
if (color[v] != 1) { V0[i] = vs[v], rea0[i] = real[v]; }
if (color[v] != 0) { V1[max(i - n0, 0)] = vs[v], rea1[max(i - n0, 0)] = real[v]; }
}
FOR(v, 1, N) {
int a = ord[v], b = ord[par[v]];
if (a > b) swap(a, b);
par2[b] = a;
if (color[v] != 1 && color[par[v]] != 1) par0[b] = a;
if (color[v] != 0 && color[par[v]] != 0) par1[max(b - n0, 0)] = max(a - n0, 0);
}
color.assign(N, -1);
FOR(i, 1, N) if (rea2[i]) color[i] = (i <= n0 ? 0 : 1);
if (real[c]) color[0] = 2, rea0[0] = rea1[0] = rea2[0] = 0;
f(par2, V2, color);
centroid_decomposition_2_dfs(par0, V0, rea0, f);
centroid_decomposition_2_dfs(par1, V1, rea1, f);
}
// 0: f(par, V, indptr)
// 1: f(par, V, L1, R1, L2, R2)
// 2: f(par, V, color)
template <int MODE, typename GT, typename F>
void centroid_decomposition(GT& G, F f) {
static_assert(!GT::is_directed);
const int N = G.N;
if (MODE != 0 && N == 1) return;
vc<int> V(N), par(N, -1);
int l = 0, r = 0;
V[r++] = 0;
while (l < r) {
int v = V[l++];
for (auto& e: G[v]) {
if (e.to != par[v]) V[r++] = e.to, par[e.to] = v;
}
}
assert(r == N);
vc<int> new_idx(N);
FOR(i, N) new_idx[V[i]] = i;
vc<int> tmp(N, -1);
FOR(i, 1, N) {
int j = par[i];
tmp[new_idx[i]] = new_idx[j];
}
swap(par, tmp);
static_assert(MODE == 0 || MODE == 1 || MODE == 2);
if constexpr (MODE == 0) { centroid_decomposition_0_dfs(par, V, f); }
elif constexpr(MODE == 1) { centroid_decomposition_1_dfs(par, V, f); }
else {
vc<int> real(N, 1);
centroid_decomposition_2_dfs(par, V, real, f);
}
}
#line 2 "/home/maspy/compro/library/mod/mod_inv.hpp"
// long でも大丈夫
// (val * x - 1) が mod の倍数になるようにする
// 特に mod=0 なら x=0 が満たす
ll mod_inv(ll val, ll mod) {
if (mod == 0) return 0;
mod = abs(mod);
val %= mod;
if (val < 0) val += mod;
ll a = val, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
swap(a -= t * b, b), swap(u -= t * v, v);
}
if (u < 0) u += mod;
return u;
}
#line 2 "/home/maspy/compro/library/mod/crt3.hpp"
constexpr u32 mod_pow_constexpr(u64 a, u64 n, u32 mod) {
a %= mod;
u64 res = 1;
FOR(32) {
if (n & 1) res = res * a % mod;
a = a * a % mod, n /= 2;
}
return res;
}
template <typename T, u32 p0, u32 p1>
T CRT2(u64 a0, u64 a1) {
static_assert(p0 < p1);
static constexpr u64 x0_1 = mod_pow_constexpr(p0, p1 - 2, p1);
u64 c = (a1 - a0 + p1) * x0_1 % p1;
return a0 + c * p0;
}
template <typename T, u32 p0, u32 p1, u32 p2>
T CRT3(u64 a0, u64 a1, u64 a2) {
static_assert(p0 < p1 && p1 < p2);
static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
static constexpr u64 p01 = u64(p0) * p1;
u64 c = (a1 - a0 + p1) * x1 % p1;
u64 ans_1 = a0 + c * p0;
c = (a2 - ans_1 % p2 + p2) * x2 % p2;
return T(ans_1) + T(c) * T(p01);
}
template <typename T, u32 p0, u32 p1, u32 p2, u32 p3>
T CRT4(u64 a0, u64 a1, u64 a2, u64 a3) {
static_assert(p0 < p1 && p1 < p2 && p2 < p3);
static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
static constexpr u64 p01 = u64(p0) * p1;
u64 c = (a1 - a0 + p1) * x1 % p1;
u64 ans_1 = a0 + c * p0;
c = (a2 - ans_1 % p2 + p2) * x2 % p2;
u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
c = (a3 - ans_2 % p3 + p3) * x3 % p3;
return T(ans_2) + T(c) * T(p01) * T(p2);
}
template <typename T, u32 p0, u32 p1, u32 p2, u32 p3, u32 p4>
T CRT5(u64 a0, u64 a1, u64 a2, u64 a3, u64 a4) {
static_assert(p0 < p1 && p1 < p2 && p2 < p3 && p3 < p4);
static constexpr u64 x1 = mod_pow_constexpr(p0, p1 - 2, p1);
static constexpr u64 x2 = mod_pow_constexpr(u64(p0) * p1 % p2, p2 - 2, p2);
static constexpr u64 x3 = mod_pow_constexpr(u64(p0) * p1 % p3 * p2 % p3, p3 - 2, p3);
static constexpr u64 x4 = mod_pow_constexpr(u64(p0) * p1 % p4 * p2 % p4 * p3 % p4, p4 - 2, p4);
static constexpr u64 p01 = u64(p0) * p1;
static constexpr u64 p23 = u64(p2) * p3;
u64 c = (a1 - a0 + p1) * x1 % p1;
u64 ans_1 = a0 + c * p0;
c = (a2 - ans_1 % p2 + p2) * x2 % p2;
u128 ans_2 = ans_1 + c * static_cast<u128>(p01);
c = static_cast<u64>(a3 - ans_2 % p3 + p3) * x3 % p3;
u128 ans_3 = ans_2 + static_cast<u128>(c * p2) * p01;
c = static_cast<u64>(a4 - ans_3 % p4 + p4) * x4 % p4;
return T(ans_3) + T(c) * T(p01) * T(p23);
}
#line 2 "/home/maspy/compro/library/poly/convolution_naive.hpp"
template <class T, typename enable_if<!has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vector<T> ans(n + m - 1);
FOR(i, n) FOR(j, m) ans[i + j] += a[i] * b[j];
return ans;
}
template <class T, typename enable_if<has_mod<T>::value>::type* = nullptr>
vc<T> convolution_naive(const vc<T>& a, const vc<T>& b) {
int n = int(a.size()), m = int(b.size());
if (n > m) return convolution_naive<T>(b, a);
if (n == 0) return {};
vc<T> ans(n + m - 1);
if (n <= 16 && (T::get_mod() < (1 << 30))) {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u64 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = sm;
}
} else {
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
u128 sm = 0;
for (int i = s; i < t; ++i) { sm += u64(a[i].val) * (b[k - i].val); }
ans[k] = T::raw(sm % T::get_mod());
}
}
return ans;
}
#line 2 "/home/maspy/compro/library/poly/convolution_karatsuba.hpp"
// 任意の環でできる
template <typename T>
vc<T> convolution_karatsuba(const vc<T>& f, const vc<T>& g) {
const int thresh = 30;
if (min(len(f), len(g)) <= thresh) return convolution_naive(f, g);
int n = max(len(f), len(g));
int m = ceil(n, 2);
vc<T> f1, f2, g1, g2;
if (len(f) < m) f1 = f;
if (len(f) >= m) f1 = {f.begin(), f.begin() + m};
if (len(f) >= m) f2 = {f.begin() + m, f.end()};
if (len(g) < m) g1 = g;
if (len(g) >= m) g1 = {g.begin(), g.begin() + m};
if (len(g) >= m) g2 = {g.begin() + m, g.end()};
vc<T> a = convolution_karatsuba(f1, g1);
vc<T> b = convolution_karatsuba(f2, g2);
FOR(i, len(f2)) f1[i] += f2[i];
FOR(i, len(g2)) g1[i] += g2[i];
vc<T> c = convolution_karatsuba(f1, g1);
vc<T> F(len(f) + len(g) - 1);
assert(2 * m + len(b) <= len(F));
FOR(i, len(a)) F[i] += a[i], c[i] -= a[i];
FOR(i, len(b)) F[2 * m + i] += b[i], c[i] -= b[i];
if (c.back() == T(0)) c.pop_back();
FOR(i, len(c)) if (c[i] != T(0)) F[m + i] += c[i];
return F;
}
#line 2 "/home/maspy/compro/library/poly/ntt.hpp"
template <class mint>
void ntt(vector<mint>& a, bool inverse) {
assert(mint::can_ntt());
const int rank2 = mint::ntt_info().fi;
const int mod = mint::get_mod();
static array<mint, 30> root, iroot;
static array<mint, 30> rate2, irate2;
static array<mint, 30> rate3, irate3;
assert(rank2 != -1 && len(a) <= (1 << max(0, rank2)));
static bool prepared = 0;
if (!prepared) {
prepared = 1;
root[rank2] = mint::ntt_info().se;
iroot[rank2] = mint(1) / root[rank2];
FOR_R(i, rank2) {
root[i] = root[i + 1] * root[i + 1];
iroot[i] = iroot[i + 1] * iroot[i + 1];
}
mint prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 2; i++) {
rate2[i] = root[i + 2] * prod;
irate2[i] = iroot[i + 2] * iprod;
prod *= iroot[i + 2];
iprod *= root[i + 2];
}
prod = 1, iprod = 1;
for (int i = 0; i <= rank2 - 3; i++) {
rate3[i] = root[i + 3] * prod;
irate3[i] = iroot[i + 3] * iprod;
prod *= iroot[i + 3];
iprod *= root[i + 3];
}
}
int n = int(a.size());
int h = topbit(n);
assert(n == 1 << h);
if (!inverse) {
int len = 0;
while (len < h) {
if (h - len == 1) {
int p = 1 << (h - len - 1);
mint rot = 1;
FOR(s, 1 << len) {
int offset = s << (h - len);
FOR(i, p) {
auto l = a[i + offset];
auto r = a[i + offset + p] * rot;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
rot *= rate2[topbit(~s & -~s)];
}
len++;
} else {
int p = 1 << (h - len - 2);
mint rot = 1, imag = root[2];
for (int s = 0; s < (1 << len); s++) {
mint rot2 = rot * rot;
mint rot3 = rot2 * rot;
int offset = s << (h - len);
for (int i = 0; i < p; i++) {
u64 mod2 = u64(mod) * mod;
u64 a0 = a[i + offset].val;
u64 a1 = u64(a[i + offset + p].val) * rot.val;
u64 a2 = u64(a[i + offset + 2 * p].val) * rot2.val;
u64 a3 = u64(a[i + offset + 3 * p].val) * rot3.val;
u64 a1na3imag = (a1 + mod2 - a3) % mod * imag.val;
u64 na2 = mod2 - a2;
a[i + offset] = a0 + a2 + a1 + a3;
a[i + offset + 1 * p] = a0 + a2 + (2 * mod2 - (a1 + a3));
a[i + offset + 2 * p] = a0 + na2 + a1na3imag;
a[i + offset + 3 * p] = a0 + na2 + (mod2 - a1na3imag);
}
rot *= rate3[topbit(~s & -~s)];
}
len += 2;
}
}
} else {
mint coef = mint(1) / mint(len(a));
FOR(i, len(a)) a[i] *= coef;
int len = h;
while (len) {
if (len == 1) {
int p = 1 << (h - len);
mint irot = 1;
FOR(s, 1 << (len - 1)) {
int offset = s << (h - len + 1);
FOR(i, p) {
u64 l = a[i + offset].val;
u64 r = a[i + offset + p].val;
a[i + offset] = l + r;
a[i + offset + p] = (mod + l - r) * irot.val;
}
irot *= irate2[topbit(~s & -~s)];
}
len--;
} else {
int p = 1 << (h - len);
mint irot = 1, iimag = iroot[2];
FOR(s, (1 << (len - 2))) {
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h - len + 2);
for (int i = 0; i < p; i++) {
u64 a0 = a[i + offset + 0 * p].val;
u64 a1 = a[i + offset + 1 * p].val;
u64 a2 = a[i + offset + 2 * p].val;
u64 a3 = a[i + offset + 3 * p].val;
u64 x = (mod + a2 - a3) * iimag.val % mod;
a[i + offset] = a0 + a1 + a2 + a3;
a[i + offset + 1 * p] = (a0 + mod - a1 + x) * irot.val;
a[i + offset + 2 * p] = (a0 + a1 + 2 * mod - a2 - a3) * irot2.val;
a[i + offset + 3 * p] = (a0 + 2 * mod - a1 - x) * irot3.val;
}
irot *= irate3[topbit(~s & -~s)];
}
len -= 2;
}
}
}
}
#line 8 "/home/maspy/compro/library/poly/convolution.hpp"
template <class mint>
vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) {
if (a.empty() || b.empty()) return {};
int n = int(a.size()), m = int(b.size());
int sz = 1;
while (sz < n + m - 1) sz *= 2;
// sz = 2^k のときの高速化。分割統治的なやつで損しまくるので。
if ((n + m - 3) <= sz / 2) {
auto a_last = a.back(), b_last = b.back();
a.pop_back(), b.pop_back();
auto c = convolution(a, b);
c.resize(n + m - 1);
c[n + m - 2] = a_last * b_last;
FOR(i, len(a)) c[i + len(b)] += a[i] * b_last;
FOR(i, len(b)) c[i + len(a)] += b[i] * a_last;
return c;
}
a.resize(sz), b.resize(sz);
bool same = a == b;
ntt(a, 0);
if (same) {
b = a;
} else {
ntt(b, 0);
}
FOR(i, sz) a[i] *= b[i];
ntt(a, 1);
a.resize(n + m - 1);
return a;
}
template <typename mint>
vector<mint> convolution_garner(const vector<mint>& a, const vector<mint>& b) {
int n = len(a), m = len(b);
if (!n || !m) return {};
static constexpr int p0 = 167772161;
static constexpr int p1 = 469762049;
static constexpr int p2 = 754974721;
using mint0 = modint<p0>;
using mint1 = modint<p1>;
using mint2 = modint<p2>;
vc<mint0> a0(n), b0(m);
vc<mint1> a1(n), b1(m);
vc<mint2> a2(n), b2(m);
FOR(i, n) a0[i] = a[i].val, a1[i] = a[i].val, a2[i] = a[i].val;
FOR(i, m) b0[i] = b[i].val, b1[i] = b[i].val, b2[i] = b[i].val;
auto c0 = convolution_ntt<mint0>(a0, b0);
auto c1 = convolution_ntt<mint1>(a1, b1);
auto c2 = convolution_ntt<mint2>(a2, b2);
vc<mint> c(len(c0));
FOR(i, n + m - 1) { c[i] = CRT3<mint, p0, p1, p2>(c0[i].val, c1[i].val, c2[i].val); }
return c;
}
vector<ll> convolution(vector<ll> a, vector<ll> b) {
int n = len(a), m = len(b);
if (!n || !m) return {};
if (min(n, m) <= 2500) return convolution_naive(a, b);
ll mi_a = MIN(a), mi_b = MIN(b);
for (auto& x: a) x -= mi_a;
for (auto& x: b) x -= mi_b;
assert(MAX(a) * MAX(b) <= 1e18);
auto Ac = cumsum<ll>(a), Bc = cumsum<ll>(b);
vi res(n + m - 1);
for (int k = 0; k < n + m - 1; ++k) {
int s = max(0, k - m + 1);
int t = min(n, k + 1);
res[k] += (t - s) * mi_a * mi_b;
res[k] += mi_a * (Bc[k - s + 1] - Bc[k - t + 1]);
res[k] += mi_b * (Ac[t] - Ac[s]);
}
static constexpr u32 MOD1 = 1004535809;
static constexpr u32 MOD2 = 1012924417;
using mint1 = modint<MOD1>;
using mint2 = modint<MOD2>;
vc<mint1> a1(n), b1(m);
vc<mint2> a2(n), b2(m);
FOR(i, n) a1[i] = a[i], a2[i] = a[i];
FOR(i, m) b1[i] = b[i], b2[i] = b[i];
auto c1 = convolution_ntt<mint1>(a1, b1);
auto c2 = convolution_ntt<mint2>(a2, b2);
FOR(i, n + m - 1) { res[i] += CRT2<u64, MOD1, MOD2>(c1[i].val, c2[i].val); }
return res;
}
template <typename mint>
vc<mint> convolution(const vc<mint>& a, const vc<mint>& b) {
int n = len(a), m = len(b);
if (!n || !m) return {};
if (mint::can_ntt()) {
if (min(n, m) <= 50) return convolution_karatsuba<mint>(a, b);
return convolution_ntt(a, b);
}
if (min(n, m) <= 200) return convolution_karatsuba<mint>(a, b);
return convolution_garner(a, b);
}
#line 3 "/home/maspy/compro/library/graph/tree_all_distances.hpp"
// sum of result array = binom(N,2)
template <typename GT>
vi tree_all_distances(GT& G) {
assert(G.is_prepared());
int N = G.N;
vi ANS(N);
auto f = [&](vc<int>& par, vc<int>& V, int L1, int R1, int L2, int R2) -> void {
int N = len(par);
vc<int> dist(N);
FOR(i, 1, N) { dist[i] = 1 + dist[par[i]]; }
int mx = MAX(dist);
vi f(1 + mx), g(1 + mx);
FOR(i, L1, R1) f[dist[i]]++;
FOR(i, L2, R2) g[dist[i]]++;
while (len(f) && f.back() == 0) POP(f);
while (len(g) && g.back() == 0) POP(g);
f = convolution(f, g);
FOR(i, len(f)) ANS[i] += f[i];
};
centroid_decomposition<1>(G, f);
ANS[1] = N - 1;
return ANS;
}
#line 8 "main.cpp"
using mint = modint998;
void solve() {
LL(N, C);
Graph<int, 0> G(N);
G.read_tree();
Tree<decltype(G)> tree(G);
// 始点 -> パスの個数と長さ
struct Data {
ll sum, cnt;
};
Data unit = {0, 0};
auto fee = [&](Data x, Data y) -> Data { return {x.sum + y.sum, x.cnt + y.cnt}; };
auto fev = [&](Data x, int v) -> Data { return x; };
// e は v に入る有向辺
auto fve = [&](Data x, auto& e) -> Data { return {x.sum + x.cnt + 1, x.cnt + 1}; };
Rerooting_dp<decltype(tree), Data> dp(tree, fee, fev, fve, unit);
mint init = 0;
{
auto F = tree_all_distances(G);
FOR(i, len(F)) { init += mint(F[i]) * mint(i * i); }
}
vi A;
FOR(v, N) {
if (G.deg(v) != 1) continue;
Data x = dp[v];
A.eb(x.sum);
}
C -= N - 1;
int n = len(A);
vi F;
mint ANS = init * init * init;
mint ans = init;
// 結局, min element 取得と +(N-1)
sort(all(A));
deque<ll> q1, q2;
for (auto& x: A) q1.eb(x);
FOR(c, C) {
bool b1 = 0;
if (q1.empty()) {}
elif (q2.empty()) { b1 = 1; }
else {
b1 = (q1.front() < q2.front());
}
ll x = (b1 ? POP(q1) : POP(q2));
ans += N - 1 + c + 2 * x;
q2.eb(x + N - 1);
ANS += ans * ans * ans;
}
print(ANS);
}
signed main() {
INT(T);
FOR(T) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4052kb
input:
2 4 3 1 4 1 3 2 1 4 4 1 4 1 3 2 1
output:
3375 25327
result:
ok 2 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
4 4 3 1 4 1 3 2 1 4 4 1 4 1 3 2 1 5 4 1 4 1 3 1 2 5 4 5 5 1 4 1 3 1 2 5 4
output:
3375 25327 54872 249984
result:
ok 4 tokens
Test #3:
score: -100
Wrong Answer
time: 2188ms
memory: 75752kb
input:
4 300000 50000000 216838 200677 44849 12926 125086 157230 26195 29767 241694 21336 21336 24457 105861 84565 184655 45583 175336 97945 286044 30927 295273 249694 109469 1566 193560 251229 176229 288707 206166 13532 166218 264413 299977 95587 159105 48116 57912 82606 97296 193689 115029 121192 68068 1...
output:
350471937 272594273 565952276 62144234
result:
wrong answer 1st words differ - expected: '968050473', found: '350471937'