結果
| 問題 |
No.1796 木上のクーロン
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2022-12-21 22:58:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,286 ms / 10,000 ms |
| コード長 | 37,310 bytes |
| コンパイル時間 | 2,206 ms |
| コンパイル使用メモリ | 117,704 KB |
| 最終ジャッジ日時 | 2025-02-09 18:11:26 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#line 2 "nachia\\array\\csr-array.hpp"
#include <utility>
#include <vector>
#include <algorithm>
namespace nachia{
template<class Elem>
class CsrArray{
public:
struct ListRange{
using iterator = typename std::vector<Elem>::iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
Elem& operator[](int i) const { return begi[i]; }
};
struct ConstListRange{
using iterator = typename std::vector<Elem>::const_iterator;
iterator begi, endi;
iterator begin() const { return begi; }
iterator end() const { return endi; }
int size() const { return (int)std::distance(begi, endi); }
const Elem& operator[](int i) const { return begi[i]; }
};
private:
int m_n;
std::vector<Elem> m_list;
std::vector<int> m_pos;
public:
CsrArray() : m_n(0), m_list(), m_pos() {}
static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
CsrArray res;
res.m_n = n;
std::vector<int> buf(n+1, 0);
for(auto& [u,v] : items){ ++buf[u]; }
for(int i=1; i<=n; i++) buf[i] += buf[i-1];
res.m_list.resize(buf[n]);
for(int i=(int)items.size()-1; i>=0; i--){
res.m_list[--buf[items[i].first]] = std::move(items[i].second);
}
res.m_pos = std::move(buf);
return res;
}
static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
CsrArray res;
res.m_n = pos.size() - 1;
res.m_list = std::move(list);
res.m_pos = std::move(pos);
return res;
}
ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
int size() const { return m_n; }
int fullSize() const { return (int)m_list.size(); }
};
} // namespace nachia
#line 3 "nachia\\tree\\centroid-decomposition.hpp"
namespace nachia{
struct CentroidDecomposition {
int n;
CsrArray<int> E;
std::vector<int> cdep;
std::vector<int> cp;
std::vector<int> cbfs;
int maxdep;
CentroidDecomposition(CsrArray<int> edges) : E(std::move(edges)){
n = E.size();
std::vector<int> Z(n, 1);
{
std::vector<int> P(n, -1);
std::vector<int> I = { 0 };
for(int i=0; i<(int)I.size(); i++){
int p = I[i];
for (int e : E[p]) if (P[p] != e) {
P[e] = p;
I.push_back(e);
}
}
for (int i=n-1; i>=1; i--) Z[P[I[i]]] += Z[I[i]];
}
cp.assign(n, -1);
cdep.assign(n, 0);
std::vector<std::pair<int, int>> I = { {0,-1} };
for(int i=0; i<(int)I.size(); i++){
int s = I[i].first;
int par = I[i].second;
while (true) {
int nx = -1;
for (int e : E[s]) if (Z[e] * 2 > Z[s]) nx = e;
if (nx == -1) break;
Z[s] -= Z[nx];
Z[nx] += Z[s];
s = nx;
}
cbfs.push_back(s);
Z[s] = 0;
if (par != -1) {
cdep[s] = cdep[par] + 1;
cp[s] = par;
}
for (int e : E[s]) if (Z[e] != 0) {
I.push_back(std::make_pair(e, s));
}
}
maxdep = 0;
for (int a : cdep) maxdep = std::max(maxdep, a);
}
struct BFSUnit {
std::vector<int> I;
std::vector<int> P;
};
BFSUnit bfs_layer(int s, int layer) {
BFSUnit res;
if (cdep[s] < layer) return res;
res.I.push_back(s);
res.P.push_back(-1);
for(int i=0; i<(int)res.I.size(); i++){
int p = res.I[i];
for (int e : E[p]) if (res.P[i] != e) {
if (cdep[e] < layer) continue;
res.I.push_back(e);
res.P.push_back(p);
}
}
return res;
}
};
} // namespace nachia
#line 4 "nachia\\graph\\graph.hpp"
#include <cassert>
#line 6 "nachia\\graph\\graph.hpp"
namespace nachia{
struct Graph {
public:
struct Edge{
int from, to;
void reverse(){ std::swap(from, to); }
};
using Base = std::vector<std::pair<int, int>>;
Graph(int n = 0, bool undirected = false) : m_n(n), m_e(), m_isUndir(undirected) {}
Graph(int n, const std::vector<std::pair<int, int>>& edges, bool undirected = false) : m_n(n), m_isUndir(undirected){
m_e.resize(edges.size());
for(std::size_t i=0; i<edges.size(); i++) m_e[i] = { edges[i].first, edges[i].second };
}
Graph(int n, const std::vector<Edge>& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {}
Graph(int n, std::vector<Edge>&& edges, bool undirected = false) : m_n(n), m_e(edges), m_isUndir(undirected) {}
int numVertices() const noexcept { return m_n; }
int numEdges() const noexcept { return int(m_e.size()); }
int addNode() noexcept { return m_n++; }
int addEdge(int from, int to){ m_e.push_back({ from, to }); return numEdges() - 1; }
Edge& operator[](int ei) noexcept { return m_e[ei]; }
const Edge& operator[](int ei) const noexcept { return m_e[ei]; }
Edge& at(int ei) { return m_e.at(ei); }
const Edge& at(int ei) const { return m_e.at(ei); }
auto begin(){ return m_e.begin(); }
auto end(){ return m_e.end(); }
auto begin() const { return m_e.begin(); }
auto end() const { return m_e.end(); }
bool isUndirected() const noexcept { return m_isUndir; }
void reverseEdges() noexcept { for(auto& e : m_e) e.reverse(); }
void contract(int newV, const std::vector<int>& mapping){
assert(numVertices() == int(mapping.size()));
for(int i=0; i<numVertices(); i++) assert(0 <= mapping[i] && mapping[i] < newV);
for(auto& e : m_e){ e.from = mapping[e.from]; e.to = mapping[e.to]; }
}
std::vector<Graph> induce(int num, const std::vector<int>& mapping) const {
int n = numVertices();
assert(n == int(mapping.size()));
for(int i=0; i<n; i++) assert(-1 <= mapping[i] && mapping[i] < num);
std::vector<int> indexV(n), newV(num);
for(int i=0; i<n; i++) if(mapping[i] >= 0) indexV[i] = newV[mapping[i]]++;
std::vector<Graph> res; res.reserve(num);
for(int i=0; i<num; i++) res.emplace_back(newV[i], isUndirected());
for(auto e : m_e) if(mapping[e.from] == mapping[e.to] && mapping[e.to] >= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]);
return res;
}
CsrArray<int> getEdgeIndexArray(bool undirected) const {
std::vector<std::pair<int, int>> src;
src.reserve(numEdges() * (undirected ? 2 : 1));
for(int i=0; i<numEdges(); i++){
auto e = operator[](i);
src.emplace_back(e.from, i);
if(undirected) src.emplace_back(e.to, i);
}
return CsrArray<int>::Construct(numVertices(), src);
}
CsrArray<int> getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); }
CsrArray<int> getAdjacencyArray(bool undirected) const {
std::vector<std::pair<int, int>> src;
src.reserve(numEdges() * (undirected ? 2 : 1));
for(auto e : m_e){
src.emplace_back(e.from, e.to);
if(undirected) src.emplace_back(e.to, e.from);
}
return CsrArray<int>::Construct(numVertices(), src);
}
CsrArray<int> getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); }
private:
int m_n;
std::vector<Edge> m_e;
bool m_isUndir;
};
} // namespace nachia
#line 4 "nachia\\fps\\formal-power-series-struct.hpp"
#include <string>
#line 6 "nachia\\fps\\formal-power-series-struct.hpp"
#include <iostream>
#line 4 "nachia\\math-modulo\\modulo-primitive-root.hpp"
namespace nachia{
template<unsigned int MOD>
struct PrimitiveRoot{
static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) {
unsigned long long res = 1, aa = a;
while(i){
if(i & 1) res = res * aa % MOD;
aa = aa * aa % MOD;
i /= 2;
}
return res;
}
static constexpr bool ExamineVal(unsigned int g){
unsigned int t = MOD - 1;
for(unsigned long long d=2; d*d<=t; d++) if(t % d == 0){
if(powm(g, (MOD - 1) / d) == 1) return false;
while(t % d == 0) t /= d;
}
if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
return true;
}
static constexpr unsigned int GetVal(){
for(unsigned int x=2; x<MOD; x++) if(ExamineVal(x)) return x;
return 0;
}
static const unsigned int val = GetVal();
};
}
#line 3 "nachia\\math\\combination.hpp"
namespace nachia{
template<class Modint>
class Comb{
private:
std::vector<Modint> F;
std::vector<Modint> iF;
public:
void extend(int newN){
int prevN = (int)F.size() - 1;
if(prevN >= newN) return;
F.resize(newN+1);
iF.resize(newN+1);
for(int i=prevN+1; i<=newN; i++) F[i] = F[i-1] * Modint::raw(i);
iF[newN] = F[newN].inv();
for(int i=newN; i>prevN; i--) iF[i-1] = iF[i] * Modint::raw(i);
}
Comb(int n = 1){
F.assign(2, Modint(1));
iF.assign(2, Modint(1));
extend(n);
}
Modint factorial(int n) const { return F[n]; }
Modint invFactorial(int n) const { return iF[n]; }
Modint invOf(int n) const { return iF[n] * F[n-1]; }
Modint comb(int n, int r) const {
if(n < 0 || n < r || r < 0) return Modint(0);
return F[n] * iF[r] * iF[n-r];
}
Modint invComb(int n, int r) const {
if(n < 0 || n < r || r < 0) return Modint(0);
return iF[n] * F[r] * F[n-r];
}
Modint perm(int n, int r) const {
if(n < 0 || n < r || r < 0) return Modint(0);
return F[n] * iF[n-r];
}
Modint invPerm(int n, int r) const {
if(n < 0 || n < r || r < 0) return Modint(0);
return iF[n] * F[n-r];
}
Modint operator()(int n, int r) const { return comb(n,r); }
};
} // namespace nachia
#line 4 "nachia\\misc\\bit-operations.hpp"
namespace nachia{
int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
return __builtin_popcountll(c);
#else
c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
c = (c * (~0ull/257)) >> 56;
return c;
#endif
}
// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return 63 - __builtin_clzll(x);
#else
int res = 0;
for(int d=32; d>=0; d>>=1) if(x >> d){ res |= d; x >>= d; }
return res;
#endif
}
// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
return __builtin_ctzll(x);
#else
return msb_idx(x & -x);
#endif
}
}
#line 2 "nachia\\fps\\ntt-interface.hpp"
namespace nachia {
template<class mint>
struct NttInterface{
template<class Iter>
void Butterfly(Iter, int) const {}
template<class Iter>
void IButterfly(Iter, int) const {}
template<class Iter>
void BitReversal(Iter a, int N) const {
for(int i=0, j=0; j<N; j++){
if(i < j) std::swap(a[i], a[j]);
for(int k = N>>1; k > (i^=k); k>>=1);
}
}
};
} // namespace nachia
#line 5 "nachia\\fps\\ntt-acl.hpp"
#include <iterator>
#line 8 "nachia\\fps\\ntt-acl.hpp"
#include <array>
namespace nachia{
constexpr int bsf_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
template <class mint>
struct NttFromAcl : NttInterface<mint> {
using u32 = unsigned int;
using u64 = unsigned long long;
static int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (u32)(n)) x++;
return x;
}
struct fft_info {
static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
std::array<mint, rank2+1> root;
std::array<mint, rank2+1> iroot;
std::array<mint, std::max(0, rank2-1)> rate2;
std::array<mint, std::max(0, rank2-1)> irate2;
std::array<mint, std::max(0, rank2-2)> rate3;
std::array<mint, std::max(0, rank2-2)> irate3;
fft_info(){
root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
iroot[rank2] = root[rank2].inv();
for(int i=rank2-1; i>=0; i--){
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];
}
}
};
template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
int len = 0;
while(len < h){
if(h-len == 1){
int p = 1 << (h-len-1);
mint rot = 1;
for(int s=0; s<(1<<len); s++){
int offset = s << (h-len);
for(int i=0; i<p; i++){
auto l = a[i+offset];
auto r = a[i+offset+p] * rot;
a[i+offset] = l+r;
a[i+offset+p] = l-r;
}
if(s+1 != (1<<len)) rot *= info.rate2[LsbIndex(~(u32)(s))];
}
len++;
} else {
int p = 1 << (h-len-2);
mint rot = 1, imag = info.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++){
auto mod2 = 1ULL * mint::mod() * mint::mod();
auto a0 = 1ULL * a[i+offset].val();
auto a1 = 1ULL * a[i+offset+p].val() * rot.val();
auto a2 = 1ULL * a[i+offset+2*p].val() * rot2.val();
auto a3 = 1ULL * a[i+offset+3*p].val() * rot3.val();
auto a1na3imag = 1ULL * mint(a1 + mod2 - a3).val() * imag.val();
auto 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);
}
if(s+1 != (1<<len)) rot *= info.rate3[LsbIndex(~(u32)(s))];
}
len += 2;
}
}
}
template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
int h = ceil_pow2(n);
static const fft_info info;
constexpr int MOD = mint::mod();
int len = h;
while(len){
if(len == 1){
int p = 1 << (h-len);
mint irot = 1;
for(int s=0; s<(1<<(len-1)); s++){
int offset = s << (h-len+1);
for(int i=0; i<p; i++){
auto l = a[i+offset];
auto r = a[i+offset+p];
a[i+offset] = l+r;
a[i+offset+p] = (u64)(MOD + l.val() - r.val()) * irot.val();
}
if(s+1 != (1<<(len-1))) irot *= info.irate2[LsbIndex(~(u32)(s))];
}
len--;
} else {
int p = 1 << (h-len);
mint irot = 1, iimag = info.iroot[2];
for(int s=0; s<(1<<(len-2)); s++){
mint irot2 = irot * irot;
mint irot3 = irot2 * irot;
int offset = s << (h-len+2);
for(int i=0; i<p; i++){
auto a0 = 1ULL * a[i+offset+0*p].val();
auto a1 = 1ULL * a[i+offset+1*p].val();
auto a2 = 1ULL * a[i+offset+2*p].val();
auto a3 = 1ULL * a[i+offset+3*p].val();
auto a2na3iimag = 1ULL * mint((MOD + a2 - a3) * iimag.val()).val();
a[i+offset] = a0 + a1 + a2 + a3;
a[i+offset+1*p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
a[i+offset+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
a[i+offset+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
}
if(s+1 != (1<<(len-2))) irot *= info.irate3[LsbIndex(~(u32)(s))];
}
len -= 2;
}
}
}
};
} // namespace nachia
#line 11 "nachia\\fps\\formal-power-series-struct.hpp"
namespace nachia {
template<class Elem, class NttInst = NttFromAcl<Elem>>
struct FormalPowerSeriesNTT {
public:
using MyType = FormalPowerSeriesNTT;
using ElemTy = Elem;
static constexpr unsigned int MOD = Elem::mod();
static const NttInst nttInst;
static const unsigned int zeta = nachia::PrimitiveRoot<MOD>::GetVal();
private:
using u32 = unsigned int;
static Elem ZeroElem() noexcept { return Elem(0); }
static Elem OneElem() noexcept { return Elem(1); }
static Comb<Elem> comb;
std::vector<Elem> a;
public:
int size() const noexcept { return a.size(); }
Elem& operator[](int x) noexcept { return a[x]; }
const Elem& operator[](int x) const noexcept { return a[x]; }
Elem get_coeff(int x) const noexcept { return (x < size()) ? a[x] : ZeroElem(); }
static Comb<Elem>& GetComb() { return comb; }
static int BestNttSize(int x) noexcept { assert(x); return 1 << MsbIndex(x*2-1); }
MyType& removeLeadingZeros(){
int newsz = size();
while(newsz && a[newsz-1].val() == 0) newsz--;
a.resize(newsz);
if((int)a.capacity() / 4 > newsz) a.shrink_to_fit();
return *this;
}
FormalPowerSeriesNTT(){ a = { }; }
FormalPowerSeriesNTT(int new_size) : a(new_size, ZeroElem()) {}
FormalPowerSeriesNTT(std::vector<Elem>&& src) : a(std::move(src)) {}
FormalPowerSeriesNTT(const std::vector<Elem>& src) : a(src) {}
MyType& ntt() {
int N = 1; while (N < (int)size()) N *= 2;
a.resize(N, ZeroElem());
nttInst.Butterfly(a.begin(), N);
return *this;
}
MyType& intt() {
nttInst.IButterfly(a.begin(), a.size());
Elem invN = Elem(size()).inv();
for(int i=0; i<size(); i++) a[i] *= invN;
return *this;
}
MyType nttDouble(MyType vanilla) const {
int n = size();
assert(n == (n&-n)); // n is a power of 2
Elem q = Elem::raw(zeta).pow((Elem::mod() - 1) / (n*2));
Elem qq = Elem::raw(1);
for(int i=0; i<n; i++){ vanilla[i] *= qq; qq *= q; }
vanilla.ntt();
MyType res = clip(0, n, 0, n*2);
for(int i=0; i<n; i++) res[n+i] = vanilla[i];
return res;
}
MyType nttDouble() const {
MyType van = clip();
van.intt();
return nttDouble(std::move(van));
}
// returns [ a[l], a[l+1], a[l+2], ... , a[r-1] ]
// a[i] = 0 ( i < 0 OR size() <= i )
MyType getSlice(int l, int r) const {
if(l >= r) return MyType();
MyType res(r - l);
for(int i=l; i<r; i++) res[i-l] = (0 <= i && i < (int)size()) ? a[i] : ZeroElem();
return res;
}
MyType clip(int srcPos = 0, int srcLen = -1, int destPos = 0, int destSize = -1) const {
int l = std::min((int)size(), srcPos);
int r = srcLen < 0 ? (int)size() : std::min((int)size(), l + srcLen);
if(destSize < 0) destSize = r - l + destPos;
int dr = std::min(r-l, destSize - destPos);
MyType res(destSize);
for(int i=0; i<dr; i++) res[destPos+i] = a[l+i];
return res;
}
// upper < 0 -> upper = lower
MyType& capSize(int lower, int upper = -1) {
if(upper < 0) upper = lower;
if(upper <= (int)size()) a.resize(upper);
if((int)size() <= lower) a.resize(lower, ZeroElem());
return *this;
}
MyType& mulEach(const MyType& other, size_t maxi = ~(size_t)0){
maxi = std::min(maxi, (size_t)std::min(size(), other.size()));
for(size_t i=0; i<maxi; i++) a[i] *= other[i];
return *this;
}
MyType& times(Elem x){
int n = size();
for(int i=0; i<n; i++) a[i] *= x;
return *this;
}
MyType& clrRange(int l, int r){
for(int i=l; i<r; i++) a[i] = 0;
return *this;
}
static MyType convolution(const MyType& a, const MyType& b, int sz = -1){
if(a.size() <= 30 || b.size() <= 30){
if(a.size() > 30) return convolution(b,a);
if(sz < 0) sz = std::max(0, a.size() + b.size() - 1);
std::vector<Elem> res(sz);
for(int i=0; i<a.size(); i++) for(int j=0; j<b.size() && i+j<sz; j++) res[i+j] += a[i] * b[j];
return res;
}
int z = a.size() + b.size() - 1;
int Z = BestNttSize(z);
if(sz == -1) sz = z;
MyType ax = a.getSlice(0, Z);
MyType bx = b.getSlice(0, Z);
ax.ntt().mulEach(bx.ntt()).intt();
if(sz != z) ax = ax.clip(0, sz);
return ax;
}
// 1
// ----- = 1 + f + f^2 + f^3 + ...
// 1-f
MyType powerSum(int sz) const {
if (sz == 0) { return {}; }
int q = std::min((int)sz, 32);
MyType x = MyType(q);
x[0] = OneElem();
for(int i=1; i<q; i++) for(int j=1; j<=std::min(i,(int)a.size()-1); j++) x[i] += x[i-j] * a[j];
while(x.size() < sz){
int hN = x.size(), N = hN*2;
MyType a = x.clip(0, hN, 0, N);
MyType b = clip(0, N, 0, N);
a.ntt();
b.ntt().mulEach(a).intt().clrRange(0,hN).ntt().mulEach(a).intt();
for(int i=0; i<hN; i++) b[i] = x[i];
std::swap(b, x);
}
if(x.size() != sz) x = x.clip(0, sz);
return x;
}
MyType inv(int sz) const {
Elem iA0 = a[0].inv();
MyType xA = clip(0, std::min(sz, size()));
xA.times(-iA0);
xA[0] = 0;
xA = xA.powerSum(sz);
return xA.times(iA0);
}
MyType& difference(){
if(size() == 0) return *this;
for(int i=0; i+1<size(); i++) a[i] = a[i+1] * Elem::raw(i+1);
capSize(0, size() - 1);
return *this;
}
MyType& integral(){
if(size() == 0){
a.push_back(ZeroElem());
return *this;
}
capSize(size()+1);
comb.extend(size());
for(int i=size()-1; i>=1; i--) a[i] = a[i-1] * comb.invOf(i);
a[0] = ZeroElem();
return *this;
}
MyType log(int sz){
assert(sz != 0);
assert(a[0].val() == 1);
return convolution(inv(sz), clip().difference(), sz-1).integral();
}
MyType exp(int sz){
MyType res = MyType(std::vector<Elem>{ OneElem() });
while(res.size() < sz){
auto z = res.size();
res = res.clip(0, z, 0, z*2);
auto tmp = res.log(z*2);
tmp[0] = -OneElem();
for(int i=0; i<z*2 && i<size(); i++) tmp[i] = tmp[i] - a[i];
auto resntt = res;
resntt.ntt().mulEach(tmp.ntt()).intt();
for(int i=z; i<z*2; i++) res[i] = -resntt[i];
}
if(sz != res.size()) res = res.clip(0, sz);
return res;
}
MyType& reverse(){ std::reverse(a.begin(), a.end()); return *this; }
MyType pow(unsigned long long k){
int n = size();
if(k == 0){ MyType res(n); res[0] = 1; return res; }
int ctz = 0;
while(ctz<n && a[ctz].val() == 0) ctz++;
if((unsigned long long)ctz >= (n-1) / k + 1) return MyType(n);
MyType res = clip(ctz, n-ctz*k);
Elem a0 = res[0];
ctz *= k; n -= ctz;
return res.times(a0.inv()).log(n).times(Elem(k)).exp(n).times(a0.pow(k)).clip(0, n, ctz);
}
auto begin(){ return a.begin(); }
auto end(){ return a.end(); }
auto begin() const { return a.begin(); }
auto end() const { return a.end(); }
std::string toString(std::string beg = "[ ", std::string delim = " ", std::string en = " ]") const {
std::string res = beg;
bool f = false;
for(auto x : a){ if(f){ res += delim; } f = true; res += std::to_string(x.val()); }
res += en;
return res;
}
std::vector<Elem> get_vector_moved(){
std::vector<Elem> res = std::move(a);
a.clear();
return res;
}
MyType axPlusB(Elem a, Elem b) const {
auto buf = MyType(size() + 1);
for(int i=0; i<size(); i++) buf[i] += this->a[i] * b;
for(int i=0; i<size(); i++) buf[i+1] += this->a[i] * a;
return buf;
}
MyType operator+(const MyType& r) const {
auto sz = std::max(this->size(), r.size());
MyType res(sz);
for(int i=0; i<this->size(); i++) res[i] += this->operator[](i);
for(int i=0; i<r.size(); i++) res[i] += r[i];
return res;
}
MyType operator-(const MyType& r) const {
auto sz = std::max(this->size(), r.size());
MyType res(sz);
for(int i=0; i<this->size(); i++) res[i] += this->operator[](i);
for(int i=0; i<r.size(); i++) res[i] -= r[i];
return res;
}
MyType operator*(const MyType& r) const {
auto res = convolution(*this, r);
return std::move(res.removeLeadingZeros());
}
MyType& operator*=(const MyType& r){ (*this) = (*this) * r; return *this; }
MyType& operator*=(Elem m){ for(size_t i=0; i<a.size(); i++) a[i] *= m; return *this; }
MyType operator*(Elem m) const { MyType b = *this; b *= m; return b; }
Elem eval(Elem x) const {
int z = size();
Elem res = 0;
for(int i=z-1; i>=0; i--) res = res * x + a[i];
return res;
}
};
template<class Elem, class NttInst> Comb<Elem> FormalPowerSeriesNTT<Elem, NttInst>::comb;
template<class Elem, class NttInst> const NttInst FormalPowerSeriesNTT<Elem, NttInst>::nttInst;
} // namespace nachia
#line 2 "nachia\\math\\ext-gcd.hpp"
#line 6 "nachia\\math\\ext-gcd.hpp"
namespace nachia{
// ax + by = gcd(a,b)
std::pair<long long, long long> ExtGcd(long long a, long long b){
long long x = 1, y = 0;
while(b){
long long u = a / b;
std::swap(a-=b*u, b);
std::swap(x-=y*u, y);
}
return std::make_pair(x, y);
}
} // namespace nachia
#line 5 "nachia\\math-modulo\\static-modint.hpp"
namespace nachia{
template<unsigned int MOD>
struct StaticModint{
private:
using u64 = unsigned long long;
unsigned int x;
public:
using my_type = StaticModint;
template< class Elem >
static Elem safe_mod(Elem x){
if(x < 0){
if(0 <= x+MOD) return x + MOD;
return MOD - ((-(x+MOD)-1) % MOD + 1);
}
return x % MOD;
}
StaticModint() : x(0){}
StaticModint(const my_type& a) : x(a.x){}
StaticModint& operator=(const my_type&) = default;
template< class Elem >
StaticModint(Elem v) : x(safe_mod(v)){}
unsigned int operator*() const noexcept { return x; }
my_type& operator+=(const my_type& r) noexcept { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
my_type operator+(const my_type& r) const noexcept { my_type res = *this; return res += r; }
my_type& operator-=(const my_type& r) noexcept { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
my_type operator-(const my_type& r) const noexcept { my_type res = *this; return res -= r; }
my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
my_type& operator*=(const my_type& r)noexcept { x = (u64)x * r.x % MOD; return *this; }
my_type operator*(const my_type& r) const noexcept { my_type res = *this; return res *= r; }
my_type pow(unsigned long long i) const noexcept {
my_type a = *this, res = 1;
while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
return res;
}
my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
unsigned int val() const noexcept { return x; }
static constexpr unsigned int mod() { return MOD; }
static my_type raw(unsigned int val) noexcept { auto res = my_type(); res.x = val; return res; }
my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};
}
#line 2 "nachia\\misc\\fastio.hpp"
#include <cstdio>
#include <cctype>
#include <cstdint>
#line 6 "nachia\\misc\\fastio.hpp"
namespace nachia{
struct CInStream{
private:
static const unsigned int INPUT_BUF_SIZE = 1 << 17;
unsigned int p = INPUT_BUF_SIZE;
static char Q[INPUT_BUF_SIZE];
public:
using MyType = CInStream;
char seekChar() noexcept {
if(p == INPUT_BUF_SIZE){
size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
if(len != INPUT_BUF_SIZE) Q[len] = '\0';
p = 0;
}
return Q[p];
}
void skipSpace() noexcept { while(isspace(seekChar())) p++; }
uint32_t nextU32() noexcept {
skipSpace();
uint32_t buf = 0;
while(true){
char tmp = seekChar();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
int32_t nextI32() noexcept {
skipSpace();
if(seekChar() == '-'){ p++; return (int32_t)(-nextU32()); }
return (int32_t)nextU32();
}
uint64_t nextU64() noexcept {
skipSpace();
uint64_t buf = 0;
while(true){
char tmp = seekChar();
if('9' < tmp || tmp < '0') break;
buf = buf * 10 + (tmp - '0');
p++;
}
return buf;
}
int64_t nextI64() noexcept {
skipSpace();
if(seekChar() == '-'){ p++; return (int64_t)(-nextU64()); }
return (int64_t)nextU64();
}
char nextChar() noexcept { skipSpace(); char buf = seekChar(); p++; return buf; }
std::string nextToken(){
skipSpace();
std::string buf;
while(true){
char ch = seekChar();
if(isspace(ch) || ch == '\0') break;
buf.push_back(ch);
p++;
}
return buf;
}
MyType& operator>>(unsigned int& dest) noexcept { dest = nextU32(); return *this; }
MyType& operator>>(int& dest) noexcept { dest = nextI32(); return *this; }
MyType& operator>>(unsigned long& dest) noexcept { dest = nextU64(); return *this; }
MyType& operator>>(long& dest) noexcept { dest = nextI64(); return *this; }
MyType& operator>>(unsigned long long& dest) noexcept { dest = nextU64(); return *this; }
MyType& operator>>(long long& dest) noexcept { dest = nextI64(); return *this; }
MyType& operator>>(std::string& dest){ dest = nextToken(); return *this; }
MyType& operator>>(char& dest) noexcept { dest = nextChar(); return *this; }
} cin;
struct FastOutputTable{
char LZ[1000][4] = {};
char NLZ[1000][4] = {};
constexpr FastOutputTable(){
using u32 = uint_fast32_t;
for(u32 d=0; d<1000; d++){
LZ[d][0] = ('0' + d / 100 % 10);
LZ[d][1] = ('0' + d / 10 % 10);
LZ[d][2] = ('0' + d / 1 % 10);
LZ[d][3] = '\0';
}
for(u32 d=0; d<1000; d++){
u32 i = 0;
if(d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
if(d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);
if(d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);
NLZ[d][i++] = '\0';
}
}
};
struct COutStream{
private:
using u32 = uint32_t;
using u64 = uint64_t;
using MyType = COutStream;
static const u32 OUTPUT_BUF_SIZE = 1 << 17;
static char Q[OUTPUT_BUF_SIZE];
static constexpr FastOutputTable TB = FastOutputTable();
u32 p = 0;
static constexpr u32 P10(u32 d){ return d ? P10(d-1)*10 : 1; }
static constexpr u64 P10L(u32 d){ return d ? P10L(d-1)*10 : 1; }
template<class T, class U> static void Fil(T& m, U& l, U x) noexcept { m = l/x; l -= m*x; }
void next_dig9(u32 x){
u32 y;
Fil(y, x, P10(6));
nextCstr(TB.LZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
public:
void nextChar(char c){
Q[p++] = c;
if(p == OUTPUT_BUF_SIZE){ fwrite(Q, p, 1, stdout); p = 0; }
}
void nextEoln(){ nextChar('\n'); }
void nextCstr(const char* s){ while(*s) nextChar(*(s++)); }
void nextU32(uint32_t x){
u32 y = 0;
if(x >= P10(9)){
Fil(y, x, P10(9));
nextCstr(TB.NLZ[y]); next_dig9(x);
}
else if(x >= P10(6)){
Fil(y, x, P10(6));
nextCstr(TB.NLZ[y]);
Fil(y, x, P10(3));
nextCstr(TB.LZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= P10(3)){
Fil(y, x, P10(3));
nextCstr(TB.NLZ[y]); nextCstr(TB.LZ[x]);
}
else if(x >= 1) nextCstr(TB.NLZ[x]);
else nextChar('0');
}
void nextI32(int32_t x){
if(x >= 0) nextU32(x);
else{ nextChar('-'); nextU32((u32)-x); }
}
void nextU64(uint64_t x){
u32 y = 0;
if(x >= P10L(18)){
Fil(y, x, P10L(18));
nextU32(y);
Fil(y, x, P10L(9));
next_dig9(y); next_dig9(x);
}
else if(x >= P10L(9)){
Fil(y, x, P10L(9));
nextU32(y); next_dig9(x);
}
else nextU32(x);
}
void nextI64(int64_t x){
if(x >= 0) nextU64(x);
else{ nextChar('-'); nextU64((u64)-x); }
}
void writeToFile(bool flush = false){
fwrite(Q, p, 1, stdout);
if(flush) fflush(stdout);
p = 0;
}
COutStream(){ Q[0] = 0; }
~COutStream(){ writeToFile(); }
MyType& operator<<(unsigned int tg){ nextU32(tg); return *this; }
MyType& operator<<(unsigned long tg){ nextU64(tg); return *this; }
MyType& operator<<(unsigned long long tg){ nextU64(tg); return *this; }
MyType& operator<<(int tg){ nextI32(tg); return *this; }
MyType& operator<<(long tg){ nextI64(tg); return *this; }
MyType& operator<<(long long tg){ nextI64(tg); return *this; }
MyType& operator<<(const std::string& tg){ nextCstr(tg.c_str()); return *this; }
MyType& operator<<(const char* tg){ nextCstr(tg); return *this; }
MyType& operator<<(char tg){ nextChar(tg); return *this; }
} cout;
char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];
} // namespace nachia
#line 7 "Main.cpp"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned int;
#define rep(i,n) for(int i=0; i<int(n); i++)
const u32 MOD = 998244353;
using Modint = nachia::StaticModint<MOD>;
using Fps = nachia::FormalPowerSeriesNTT<Modint>;
int N;
vector<Modint> Q;
nachia::CsrArray<int> E;
Modint k0;
vector<Modint> inv_mod;
Fps C;
vector<Fps> nttC;
vector<Modint> ans;
vector<int> bfsbuf_dist;
void get_bfsbuf_dist(nachia::CentroidDecomposition::BFSUnit tree){
bfsbuf_dist[tree.I.front()] = 0;
for(int i=1; i<(int)tree.I.size(); i++){
bfsbuf_dist[tree.I[i]] = bfsbuf_dist[tree.P[i]] + 1;
}
}
Fps sigma(const Fps& B){
int n = B.size() + 2;
if(n >= 10){
int Z = 1, d = 0;
while(Z < n){ Z *= 2; d++; }
Fps revB(Z*2);
rep(i, B.size()) revB[Z-i] = B[i];
revB.ntt().mulEach(nttC[d+1]).intt();
return revB.clip(Z, n);
}
Fps ans(n);
for(int i=0; i<n; i++) for(int j=0; j<(int)B.size(); j++) ans[i] += C[i+j] * B[j];
return ans;
}
Fps sigma_tree(const nachia::CentroidDecomposition::BFSUnit& tree){
Fps dist_freq(tree.I.size());
get_bfsbuf_dist(tree);
for(int p : tree.I) dist_freq[bfsbuf_dist[p]] += Q[p];
dist_freq.removeLeadingZeros();
return sigma(dist_freq);
}
int main() {
using nachia::cin;
using nachia::cout;
cin >> N;
Q.resize(N);
rep(i,N) Q[i] = Modint::raw(cin.nextU32());
{
nachia::Graph graph(N);
rep(i,N-1){
int u,v; cin >> u >> v; u--; v--;
graph.addEdge(u, v);
}
E = graph.getAdjacencyArray(true);
}
int max_ntt_size_log = 0;
while((1 << max_ntt_size_log) < N + 6) max_ntt_size_log++;
max_ntt_size_log++;
int max_ntt_size = 1 << max_ntt_size_log;
k0 = 1;
for(int i=1; i<=N; i++) k0 = k0 * Modint::raw(i);
k0 = k0 * k0;
inv_mod.assign(max_ntt_size+1, 1);
for(int i=2; i<=max_ntt_size; i++) inv_mod[i] = - inv_mod[MOD % i] * (MOD / i);
C = Fps(max_ntt_size);
for(int i=0; i<max_ntt_size; i++) C[i] = k0 * inv_mod[i+1] * inv_mod[i+1];
nttC.resize(max_ntt_size_log+1);
for(int d=0; d<=max_ntt_size_log; d++){
nttC[d] = C.clip(0, 1<<d);
nttC[d].ntt();
}
bfsbuf_dist.assign(N, 0);
ans.assign(N, 0);
auto centroid_decomposition = nachia::CentroidDecomposition(E);
for(int s=0; s<N; s++){
int dep_s = centroid_decomposition.cdep[s];
auto bfs_s = centroid_decomposition.bfs_layer(s, dep_s);
Fps sigma_s = sigma_tree(bfs_s);
for(int nx : E[s]) if(centroid_decomposition.cdep[nx] > dep_s){
nachia::CentroidDecomposition::BFSUnit bfs_nx = centroid_decomposition.bfs_layer(nx, dep_s+1);
Fps sigma_nx = sigma_tree(bfs_nx);
for(int p : bfs_nx.I){
int d = bfsbuf_dist[p] + 1;
ans[p] += sigma_s[d] - sigma_nx[d+1];
}
}
ans[s] += sigma_s[0];
}
rep(p,N) cout << ans[p].val() << "\n";
return 0;
}