#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } using namespace std; #include using Modint = atcoder::static_modint<998244353>; #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::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::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 m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector 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 list, std::vector 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 #include namespace nachia{ struct Graph { public: struct Edge{ int from, to; void reverse(){ std::swap(from, to); } int xorval() const { return from ^ to; } }; Graph(int n = 0, bool undirected = false, int m = 0) : m_n(n), m_e(m), m_isUndir(undirected) {} Graph(int n, const std::vector>& edges, int undirected = false) : m_n(n), m_isUndir(undirected){ m_e.resize(edges.size()); for(std::size_t i=0; i static Graph Input(Cin& cin, int n, bool undirected, int m, int offset = 0){ Graph res(n, undirected, m); for(int i=0; i> u >> v; res[i].from = u - offset; res[i].to = v - offset; } return res; } 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& mapping){ assert(numVertices() == int(mapping.size())); for(int i=0; i induce(int num, const std::vector& mapping) const { int n = numVertices(); assert(n == int(mapping.size())); for(int i=0; i indexV(n), newV(num); for(int i=0; i= 0) indexV[i] = newV[mapping[i]]++; std::vector res; res.reserve(num); for(int i=0; i= 0) res[mapping[e.to]].addEdge(indexV[e.from], indexV[e.to]); return res; } CsrArray getEdgeIndexArray(bool undirected) const { std::vector> src; src.reserve(numEdges() * (undirected ? 2 : 1)); for(int i=0; i::Construct(numVertices(), src); } CsrArray getEdgeIndexArray() const { return getEdgeIndexArray(isUndirected()); } CsrArray getAdjacencyArray(bool undirected) const { std::vector> 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::Construct(numVertices(), src); } CsrArray getAdjacencyArray() const { return getAdjacencyArray(isUndirected()); } private: int m_n; std::vector m_e; bool m_isUndir; }; } // namespace nachia namespace nachia{ struct HeavyLightDecomposition{ private: int N; std::vector P; std::vector PP; std::vector PD; std::vector D; std::vector I; std::vector rangeL; std::vector rangeR; public: HeavyLightDecomposition(const CsrArray& E = CsrArray::Construct(1, {}), int root = 0){ N = E.size(); P.assign(N, -1); I.assign(N, 0); I[0] = root; int iI = 1; for(int i=0; i Z(N, 1); std::vector nx(N, -1); PP.resize(N); for(int i=0; i=1; i--){ int p = I[i]; Z[P[p]] += Z[p]; if(nx[P[p]] == -1) nx[P[p]] = p; if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } for(int p : I) if(nx[p] != -1) PP[nx[p]] = p; PD.assign(N,N); PD[root] = 0; D.assign(N,0); for(int p : I) if(p != root){ PP[p] = PP[PP[p]]; PD[p] = std::min(PD[PP[p]], PD[P[p]]+1); D[p] = D[P[p]]+1; } rangeL.assign(N,0); rangeR.assign(N,0); for(int p : I){ rangeR[p] = rangeL[p] + Z[p]; int ir = rangeR[p]; for(int e : E[p]) if(P[p] != e) if(e != nx[p]){ rangeL[e] = (ir -= Z[e]); } if(nx[p] != -1){ rangeL[nx[p]] = rangeL[p] + 1; } } for(int i=0; i PD[v]) u = P[PP[u]]; while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; } return (D[u] > D[v]) ? v : u; } int dist(int u, int v) const { return depth(u) + depth(v) - depth(lca(u,v)) * 2; } struct Range{ int l; int r; int size() const { return r-l; } bool includes(int x) const { return l <= x && x < r; } }; std::vector path(int r, int c, bool include_root = true, bool reverse_path = false) const { if(PD[c] < PD[r]) return {}; std::vector res(PD[c]-PD[r]+1); for(int i=0; i<(int)res.size()-1; i++){ res[i] = { rangeL[PP[c]], rangeL[c]+1 }; c = P[PP[c]]; } if(PP[r] != PP[c] || D[r] > D[c]) return {}; res.back() = { rangeL[r]+(include_root?0:1), rangeL[c]+1 }; if(res.back().l == res.back().r) res.pop_back(); if(!reverse_path) std::reverse(res.begin(),res.end()); else for(auto& a : res) a = { N - a.r, N - a.l }; return res; } Range subtree(int p) const { return { rangeL[p], rangeR[p] }; } int median(int x, int y, int z) const { return lca(x,y) ^ lca(y,z) ^ lca(x,z); } int la(int from, int to, int d) const { if(d < 0) return -1; int g = lca(from,to); int dist0 = D[from] - D[g] * 2 + D[to]; if(dist0 < d) return -1; int p = from; if(D[from] - D[g] < d){ p = to; d = dist0 - d; } while(D[p] - D[PP[p]] < d){ d -= D[p] - D[PP[p]] + 1; p = P[PP[p]]; } return I[rangeL[p] - d]; } struct ChildrenIterRange { struct Iter { const HeavyLightDecomposition& hld; int s; int operator*() const { return hld.toVtx(s); } Iter& operator++(){ s += hld.subtree(hld.I[s]).size(); return *this; } Iter operator++(int) const { auto a = *this; return ++a; } bool operator==(Iter& r) const { return s == r.s; } bool operator!=(Iter& r) const { return s != r.s; } }; const HeavyLightDecomposition& hld; int v; Iter begin() const { return { hld, hld.rangeL[v] + 1 }; } Iter end() const { return { hld, hld.rangeR[v] }; } }; ChildrenIterRange children(int v) const { return ChildrenIterRange{ *this, v }; } }; } // namespace nachia void testcase(){ int N; cin >> N; auto tree = nachia::Graph::Input(cin, N, true, N-1, 1); auto hld = nachia::HeavyLightDecomposition(tree, 0); vector F(N+1); F[0] = 1; for(int i=1; i<=N; i++) F[i] = F[i-1] * i; Modint ans = 1; rep(v,N){ int c = 0; for(auto w : hld.children(v)) c++; if(v == 0){ ans *= F[c]; } else { ans *= F[c+1]; } } ans /= F[N-1]; cout << ans.val() << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }