#include #include namespace nachia{ struct AdjacencyList{ public: struct AdjacencyListRange{ using iterator = typename std::vector::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 int& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyList(int n, std::vector> edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = v; if(rev) E[--buf[v]] = u; } I = std::move(buf); } AdjacencyList(const std::vector>& edges = {}){ int n = mn = edges.size(); std::vector buf(n+1, 0); for(int i=0; i targets, std::vector bounds){ AdjacencyList res; res.mn = bounds.size() - 1; res.E = std::move(targets); res.I = std::move(bounds); return res; } AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyList reversed_edges() const { AdjacencyList res; int n = res.mn = mn; std::vector buf(n+1, 0); for(int v : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u::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 Edge& operator[](int i) const { return begi[i]; } }; private: int mn; std::vector E; std::vector I; public: AdjacencyListEdgeIndexed(int n, const std::vector>& edges, bool rev){ mn = n; std::vector buf(n+1, 0); for(auto [u,v] : edges){ ++buf[u]; if(rev) ++buf[v]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; E.resize(buf[n]); for(int i=(int)edges.size()-1; i>=0; i--){ auto [u,v] = edges[i]; E[--buf[u]] = { v, i }; if(rev) E[--buf[v]] = { u, i }; } I = std::move(buf); } AdjacencyListEdgeIndexed() : AdjacencyListEdgeIndexed(0, {}, false) {} AdjacencyListRange operator[](int u) const { return AdjacencyListRange{ E.begin() + I[u], E.begin() + I[u+1] }; } int num_vertices() const { return mn; } int size() const { return num_vertices(); } int num_edges() const { return E.size(); } AdjacencyListEdgeIndexed reversed_edges() const { AdjacencyListEdgeIndexed res; int n = res.mn = mn; std::vector buf(n+1, 0); for(auto [v,i] : E) ++buf[v]; for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.E.resize(buf[n]); for(int u=0; u 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 examine_val(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 get_val(){ for(unsigned int x=2; x namespace nachia{ namespace freq_table_of_tree_dist_internal{ // a^i mod M template unsigned int powm(unsigned int a, unsigned long long i) { if(i == 0) return 1; unsigned int r = powm((unsigned long long)a*a%MOD,i/2); if(i&1) r = (unsigned long long)r*a%MOD; return r; } template void NTT(std::vector& A){ int N = 1; while (N < (int)A.size()) N *= 2; static std::vector exp_i_revbit_diff = { (unsigned int)powm(g, (MOD - 1) >> 2) }; for(int i=exp_i_revbit_diff.size(); (1<<(i+1))(g, (MOD - 1) / 2 + ((MOD - 1) >> (i+2)) * 3); exp_i_revbit_diff.push_back(diffdiff); } for (int i = 1; i < N; i <<= 1) { unsigned long long q = 1; int maxk = N / i / 2; for (int j = 0; j < i; j++) { int off = j * maxk * 2; for (int k = off; k < off + maxk; k++) { unsigned int l = A[k]; unsigned int r = A[k + maxk] * q % MOD; A[k] = std::min(l + r - MOD, l + r); A[k + maxk] = std::min(l - r, l + MOD - r); } if(j+1 != i) for(int d=0; ; d++) if(!(j&(1<> 1; k > (i ^= k); k >>= 1); } } template std::vector convolution_static(const std::vector& A, const std::vector& B){ constexpr unsigned int g = nachia::PrimitiveRoot::get_val(); int Z = 1; while(Z < (int)(A.size() + B.size() - 1)) Z *= 2; std::vector Ax(Z), Bx(Z); unsigned long long iZ = powm(Z, MOD - 2); for(int i=0; i<(int)A.size(); i++) Ax[i] = A[i]; for(int i=0; i<(int)B.size(); i++) Bx[i] = B[i]; NTT(Ax); NTT(Bx); for(int i=0; i(Ax); reverse(Ax.begin() + 1, Ax.end()); for(int i=0; i convolution(const std::vector& A, const std::vector& B){ if(500 / A.size() >= B.size()){ std::vector res(A.size() + B.size() - 1); for(std::size_t i=0; i res0 = convolution_static(A,B); std::vector res1 = convolution_static(A,B); std::vector res(res0.size()); unsigned long long t = powm(MOD0, MOD1-2); for(int i=0; i<(int)res.size(); i++){ unsigned long long x = res1[i] + MOD1 - res0[i]; if(x >= MOD1) x -= MOD1; x = x * t % MOD1; res[i] = res0[i] + x * MOD0; } return res; } struct FrequencyTableOfTreeDistance{ std::vector ans; std::vector> anstmp0; std::vector> anstmp1; static constexpr unsigned int NTTg0 = nachia::PrimitiveRoot::get_val(); static constexpr unsigned int NTTg1 = nachia::PrimitiveRoot::get_val(); void complete_ans(){ unsigned long long t = powm(MOD0, MOD1-2); for(int i=0; i<(int)anstmp0.size(); i++){ if(anstmp0[i].empty()) continue; int n = anstmp0[i].size(); NTT(anstmp0[i]); std::reverse(anstmp0[i].begin()+1, anstmp0[i].end()); NTT(anstmp1[i]); std::reverse(anstmp1[i].begin()+1, anstmp1[i].end()); for(int j=0; j(n, ans.size()); j++){ unsigned long long x = anstmp1[i][j] + MOD1 - anstmp0[i][j]; if(x >= MOD1) x -= MOD1; x = x * t % MOD1; ans[j] += anstmp0[i][j] + x * MOD0; } anstmp0[i].clear(); anstmp1[i].clear(); } } void append_convolute_once(std::vector a, std::vector b){ int Z = 1, dZ = 0; while(Z < (int)(a.size() + b.size() - 1)){ Z *= 2; dZ++; } a.resize(Z, 0); b.resize(Z, 0); unsigned int invZ1 = powm(Z, MOD1-2); NTT(a); NTT(b); for(int i=0; i<(int)a.size(); i++) a[i] = (unsigned long long)a[i] * b[i] % MOD1 * invZ1 % MOD1; NTT(a); std::reverse(a.begin()+1, a.end()); for(int i=0; i<(int)a.size(); i++) ans[i] += a[i]; } void append_convolute(std::vector a, std::vector b){ if((unsigned long long)a.size() * b.size() < 200){ for(std::size_t i=0; i(Z, MOD0-2); unsigned int invZ1 = powm(Z, MOD1-2); if(anstmp0[dZ].empty()){ anstmp0[dZ].assign(Z, 0); anstmp1[dZ].assign(Z, 0); } a.resize(Z, 0); b.resize(Z, 0); std::vector acpy = a; std::vector bcpy = b; NTT(a); NTT(b); for(std::size_t i=0; i(a); NTT(b); for(std::size_t i=0; i solve(const nachia::AdjacencyList& E){ int n = E.num_vertices(); int ceillog2n = 1; while(1 << ceillog2n < n) ceillog2n++; anstmp0.resize(ceillog2n + 2); anstmp1.resize(ceillog2n + 2); std::vector Z(n,1); ans.resize(n,0); { std::vector bfs = {0}; bfs.reserve(n); std::vector P(n, -1); for(int i=0; i=1; i--) Z[P[bfs[i]]] += Z[bfs[i]]; } auto dfsmain = [&](int s, auto dfsmain)->void { if(Z[s] == 1){ Z[s] = 0; return; } while(true){ int mxz = E[s].begin()[0]; for(int e : E[s]) if(Z[e] > Z[mxz]) mxz = e; if(Z[mxz] * 2 > Z[s]){ Z[s] -= Z[mxz]; Z[mxz] += Z[s]; s = mxz; } else break; } Z[s] = 0; std::vector> dcnt; std::vector dcnt_sum; for(int s2 : E[s]) if(Z[s2] != 0){ std::vector I = {s2}; std::vector D = {1}; std::vector P = {-1}; for(int i=0; i<(int)I.size(); i++){ int p = I[i]; for(int e : E[p]) if(e != P[i]) if(Z[e] != 0){ I.push_back(e); D.push_back(D[i]+1); P.push_back(p); } } std::vector tmp(D.back()+1); for(int d : D) tmp[d]++; dcnt.emplace_back(std::move(tmp)); dcnt_sum.emplace_back(Z[s2]); } std::sort(dcnt.begin(), dcnt.end(), [](const std::vector& l, const std::vector& r)->bool { return l.size() < r.size(); } ); int dcnt_sum_sum = dcnt_sum[0]; for(std::size_t i=0; i dcnt_sum[i+1]) append_convolute_once(dcnt[i+1], dcnt[i]); else append_convolute(dcnt[i+1], dcnt[i]); for(std::size_t k=0; k FrequencyTableOfTreeDistance(const nachia::AdjacencyList& T){ return freq_table_of_tree_dist_internal::FrequencyTableOfTreeDistance().solve(T); } } // namespace nachia #include #define rep(i,n) for(int i=0; i<(n); i++) int main(){ using namespace std; int N; cin >> N; std::vector> E(N-1); rep(i,N-1){ int u,v; cin >> u >> v; E[i] = make_pair(u,v); } auto ans = nachia::FrequencyTableOfTreeDistance(nachia::AdjacencyList(N,E,true)); for(int i=1; i<=N-1; i++){ if(i == 2) cout << ans[i]; } cout << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;