// GPT-o4-mini-highによる生成コード #include using namespace std; static const int MOD = 998244353; static const int G = 3; // primitive root // Fast exponentiation modulo MOD int modpow(int a, long long e) { long long r = 1, x = a; while (e) { if (e & 1) r = r * x % MOD; x = x * x % MOD; e >>= 1; } return int(r); } // ----- NTT (in-place) ----- void ntt(vector& a, bool invert) { int n = a.size(); static vector rev; static vector roots{0,1}; // build bit-reversed indices if ((int)rev.size() != n) { int k = __builtin_ctz(n); rev.assign(n, 0); for (int i = 0; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (k - 1)); } for (int i = 0; i < n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]); // build roots of unity if ((int)roots.size() < n) { int k = __builtin_ctz(roots.size()); roots.resize(n); while ((1 << k) < n) { int e = modpow(G, (MOD - 1) >> (k + 1)); for (int i = 1 << (k - 1); i < (1 << k); i++) { roots[2 * i] = roots[i]; roots[2 * i + 1] = int((long long)roots[i] * e % MOD); } k++; } } // Cooley–Tukey for (int len = 1; len < n; len <<= 1) { for (int i = 0; i < n; i += 2 * len) { for (int j = 0; j < len; j++) { int u = a[i + j]; int v = int((long long)a[i + j + len] * roots[len + j] % MOD); a[i + j] = u + v < MOD ? u + v : u + v - MOD; a[i + j + len] = u - v >= 0 ? u - v : u - v + MOD; } } } if (invert) { reverse(a.begin() + 1, a.end()); int inv_n = modpow(n, MOD - 2); for (int &x : a) x = int((long long)x * inv_n % MOD); } } // multiply two polynomials via NTT vector multiply(const vector& A, const vector& B) { int need = int(A.size() + B.size()) - 1; int n = 1; while (n < need) n <<= 1; vector fa(A.begin(), A.end()), fb(B.begin(), B.end()); fa.resize(n); fb.resize(n); ntt(fa, false); ntt(fb, false); for (int i = 0; i < n; i++) fa[i] = int((long long)fa[i] * fb[i] % MOD); ntt(fa, true); fa.resize(need); return fa; } // factorials and inverse factorials vector fact, invfact; void init_factorials(int n) { fact.assign(n + 1, 1); for (int i = 1; i <= n; i++) fact[i] = int((long long)fact[i - 1] * i % MOD); invfact.assign(n + 1, 1); invfact[n] = modpow(fact[n], MOD - 2); for (int i = n; i > 0; i--) invfact[i - 1] = int((long long)invfact[i] * i % MOD); } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N, S, T; cin >> N >> S >> T; vector U(N), V(N); vector>> adj(N+1); for(int i = 1; i <= N-1; i++){ cin >> U[i] >> V[i]; adj[U[i]].emplace_back(V[i], i); adj[V[i]].emplace_back(U[i], i); } // --- Build LCA structure on vertices --- int LOG = __lg(N) + 2; vector depth(N+1, 0); vector> up(LOG, vector(N+1, 0)); function dfs = [&](int u, int p){ up[0][u] = p; for (auto &pr : adj[u]){ int v = pr.first; if (v == p) continue; depth[v] = depth[u] + 1; dfs(v, u); } }; dfs(1, 0); for (int k = 1; k < LOG; k++){ for (int v = 1; v <= N; v++){ up[k][v] = up[k-1][ up[k-1][v] ]; } } auto lca = [&](int a, int b){ if (depth[a] < depth[b]) swap(a,b); int d = depth[a] - depth[b]; for (int k = 0; k < LOG; k++) if (d >> k & 1) a = up[k][a]; if (a == b) return a; for (int k = LOG-1; k >= 0; k--){ if (up[k][a] != up[k][b]){ a = up[k][a]; b = up[k][b]; } } return up[0][a]; }; auto dist = [&](int a, int b){ int w = lca(a,b); return depth[a] + depth[b] - 2*depth[w]; }; // Determine which endpoints of edges S and T give minimal vertex-distance int us = U[S], vs = V[S], ut = U[T], vt = V[T]; array>,4> cand = {{ {dist(us,ut),{us,ut}}, {dist(us,vt),{us,vt}}, {dist(vs,ut),{vs,ut}}, {dist(vs,vt),{vs,vt}} }}; sort(cand.begin(), cand.end(), [](auto &a, auto &b){ return a.first < b.first; }); int D = cand[0].first; int p = cand[0].second.first; int q = cand[0].second.second; int L = D + 2; // minimal number of stages // Retrieve the unique simple path of vertices from p to q vector path_u, path_v; int w = lca(p, q); for (int x = p; x != w; x = up[0][x]) path_u.push_back(x); path_u.push_back(w); for (int x = q; x != w; x = up[0][x]) path_v.push_back(x); reverse(path_v.begin(), path_v.end()); for (int x : path_v) path_u.push_back(x); // path_u is now the vertex-path from p to q // Collect the edge-indices along that vertex-path vector vertexPathEdges; vertexPathEdges.reserve(path_u.size()-1); for (int i = 0; i + 1 < (int)path_u.size(); i++){ int a = path_u[i], b = path_u[i+1]; // find the edge index a--b for (auto &pr : adj[a]){ if (pr.first == b){ vertexPathEdges.push_back(pr.second); break; } } } // Build the "main path" of edges from S to T vector mainEdges; mainEdges.reserve(vertexPathEdges.size() + 2); mainEdges.push_back(S); for (int e : vertexPathEdges){ if (e != S && e != T) mainEdges.push_back(e); } mainEdges.push_back(T); // Now mainEdges.size() == L // Gather the (deg-2) counts for each segment between consecutive main-edges vector xs; xs.reserve(mainEdges.size()); for (int i = 0; i + 1 < (int)mainEdges.size(); i++){ int e1 = mainEdges[i], e2 = mainEdges[i+1]; // find their shared vertex int a1 = U[e1], b1 = V[e1]; int a2 = U[e2], b2 = V[e2]; int shared = (a1==a2||a1==b2) ? a1 : b1; int d = adj[shared].size(); int x = d - 2; if (x > 0) xs.push_back(x); } // If no segments have extra branches, the only path is the minimal one if (xs.empty()) { for (int k = 1; k <= N; k++){ cout << (k==L ? 1 : 0) << (k==N?'\n':' '); } return 0; } // Precompute factorials up to max(xs) int mx = *max_element(xs.begin(), xs.end()); init_factorials(mx); // Build each polynomial f_i(t) of degree x: f_i[k] = P(x, k) = x*(x-1)*...*(x-k+1) vector> polys; polys.reserve(xs.size()); for (int x : xs){ vector p(x+1, 0); // p[k] = fact[x] * invfact[x-k] mod for (int k = 0; k <= x; k++){ p[k] = int((long long)fact[x] * invfact[x - k] % MOD); } polys.push_back(move(p)); } // Multiply all polynomials via a min‑heap to merge smallest first auto cmp = [&](const vector& A, const vector& B){ return A.size() > B.size(); }; priority_queue, vector>, decltype(cmp)> pq(cmp); for (auto &p : polys) pq.push(p); while (pq.size() > 1) { auto A = move(const_cast&>(pq.top())); pq.pop(); auto B = move(const_cast&>(pq.top())); pq.pop(); vector C; // Fast paths for very small or scalar polys: if (A.size() == 1) { int c0 = A[0]; C = B; if (c0 != 1) for (int &v : C) v = int((long long)v * c0 % MOD); } else if (B.size() == 1) { int c0 = B[0]; C = A; if (c0 != 1) for (int &v : C) v = int((long long)v * c0 % MOD); } else if ((long long)A.size() * B.size() < 4096) { // naive O(n*m) convolution for small sizes C.assign(A.size() + B.size() - 1, 0); for (int i = 0; i < (int)A.size(); i++) for (int j = 0; j < (int)B.size(); j++) C[i+j] = (C[i+j] + (long long)A[i] * B[j]) % MOD; } else { // use NTT C = multiply(A, B); } pq.push(move(C)); } auto F = pq.top(); // the full generating function // Prepare answers: f[k] = coefficient of t^(k-L) in F, for k >= L vector ans(N+1, 0); for (int k = L; k <= N; k++){ int idx = k - L; if (idx < (int)F.size()) ans[k] = F[idx]; } // Output for (int k = 1; k <= N; k++){ cout << ans[k] << (k==N?'\n':' '); } return 0; }