// -fsanitize=undefined, // #define _GLIBCXX_DEBUG #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; #define rep(i,n) for (int i=0;i-1;i--) #define pb push_back #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n"; template using vec = vector; template using vvec = vec>; template using vvvec = vec>; using ll = long long; using pii = pair; using pll = pair; template bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template bool chmax(T &a, T b){ if (a T sum(vec x){ T res=0; for (auto e:x){ res += e; } return res; } template void printv(vec x){ for (auto e:x){ cout< ostream& operator<<(ostream& os, const pair& A){ os << "(" << A.first <<", " << A.second << ")"; return os; } template ostream& operator<<(ostream& os, const set& S){ os << "set{"; for (auto a:S){ os << a; auto it = S.find(a); it++; if (it!=S.end()){ os << ", "; } } os << "}"; return os; } using mint = modint998244353; ostream& operator<<(ostream& os, const mint& a){ os << a.val(); return os; } template ostream& operator<<(ostream& os, const vec& A){ os << "["; rep(i,A.size()){ os << A[i]; if (i!=A.size()-1){ os << ", "; } } os << "]" ; return os; } template vector& operator+=(vector& a, const vector& b) { if (a.size() < b.size()) { a.resize(b.size()); } for (int i = 0; i < (int)b.size(); i++) { a[i] += b[i]; } return a; } template vector operator+(const vector& a, const vector& b) { vector c = a; return c += b; } vector calc_prod(vector> polys){ if (polys.empty()) return {1}; deque> deq; for (auto f:polys) deq.push_back(f); while (deq.size() > 1){ auto f = deq.front(); deq.pop_front(); auto g = deq.front(); deq.pop_front(); deq.push_back(convolution(f,g)); } return deq[0]; } pair,vector> merge_child(vector,vec>> child_polys){ if (child_polys.empty()){ return {{1},{1,-1}}; } deque,vec>> deq; for (auto e:child_polys) deq.push_back(e); while (deq.size() > 1){ auto [f0,f1] = deq.front(); deq.pop_front(); auto [g0,g1] = deq.front(); deq.pop_front(); auto h1 = convolution(f1,g1); auto h0 = convolution(g0,f1) + convolution(f0,g1); deq.push_back({h0,h1}); } auto [A,B] = deq.front(); vector res0 = B; /*res1 = A * (-x^2) + B * (1-x) */ //debug(child_polys); //debug(A); //debug(B); vector res1(max(A.size()+2,B.size()+1),0); rep(i,A.size()) res1[i+2] -= A[i]; rep(i,B.size()) { res1[i] += B[i]; res1[i+1] -= B[i]; } return {res0,res1}; } pair,vector> merge_path(vector,vector>> polys){ int n = polys.size(); if (n & 1){ polys.push_back({{0},{1}}); } n = polys.size(); //debug(polys); vector,4>> nxt_polys; for (int i=0;i00 or 11(-x^2倍) 0+1->01 1+0->10 1+1->11 */ auto [f0,f1] = polys[i]; auto [g0,g1] = polys[i+1]; array,4> merge; merge[1] = convolution(f0,g1); merge[2] = convolution(f1,g0); merge[3] = convolution(f1,g1); auto h = convolution(f0,g0); merge[0] = h; int p = h.size(); if (merge[3].size() < p+2){ merge[3].resize(p+2); } rep(i,p) merge[3][i+2] -= h[i]; nxt_polys.push_back(merge); } auto calc = [&](auto self,int l,int r)->array,4> { if (r-l==1){ return nxt_polys[l]; } int mid = (l+r)>>1; auto left = self(self,l,mid); auto right = self(self,mid,r); int merge_n = 0; rep(i,4){ rep(j,4){ int nxt_ocu = (i & 2) + (j & 1); int mid_ocu = (i & 1) + (j & 2); int h_deg = left[i].size() + right[j].size() - 2; //debug(i); //debug(j); //debug(h_deg); if (mid_ocu == 0){ chmax(merge_n,h_deg+2); } else if (mid_ocu == 3){ chmax(merge_n,h_deg); } } } merge_n += 1; //debug(merge_n); array,4> merge; rep(i,4) merge[i] = vector(merge_n,0); rep(i,4){ rep(j,4){ int nxt_ocu = (i & 2) + (j & 1); int mid_ocu = (i & 1) + (j & 2); if (mid_ocu!=0 && mid_ocu!=3) continue; auto h = convolution(left[i],right[j]); //assert ((h.size()-1) == left[i].size() + right[j].size() - 2); if (mid_ocu == 0){ //assert (h.size()+1 < merge_n); rep(k,h.size()){ merge[nxt_ocu][k+2] -= h[k]; } } else if (mid_ocu == 3){ //debug(i); //debug(j); //debug(h.size()); //assert (h.size()-1 < merge_n); rep(k,h.size()){ merge[nxt_ocu][k] += h[k]; } } } } return merge; }; auto merged = calc(calc,0,nxt_polys.size()); vector res0 = merged[1], res1 = merged[3]; return {res0,res1}; } mint BostanMori2(vec P,vec Q, long long N){ for (; N; N>>= 1){ vec Q_neg = {all(Q)}; for (int i=1;i nxt_P((deg_P/2+1),0),nxt_Q((deg_Q/2+1),0); for (int i = (N & 1);i <= deg_P; i+=2){ nxt_P[i>>1] = P[i]; } for (int i = 0; i <= deg_Q; i+=2){ nxt_Q[i>>1] = Q[i]; } swap(P,nxt_P); swap(Q,nxt_Q); } return P[0]; } void solve(){ int N,M,S,T; cin>>N>>M>>S>>T; S--; T--; vec> edge(N); rep(i,N-1){ int a,b; cin>>a>>b; a--; b--; edge[a].push_back(b); edge[b].push_back(a); } vec parent(N,-1), sz(N,1); vec heavy_child(N,-1); int root = T; auto dfs0 = [&](auto self,int v,int pv)->void { int tmp_max_sz = 0; for (auto nv:edge[v]){ if (nv == pv) continue; parent[nv] = v; self(self,nv,v); sz[v] += sz[nv]; if (sz[nv] > tmp_max_sz){ tmp_max_sz = sz[nv]; heavy_child[v] = nv; } } }; dfs0(dfs0,root,-1); vector on_st_path(N,0); on_st_path[T] = 1; { int pos = S; while (pos!=T){ on_st_path[pos] = 1; pos = parent[pos]; } } vector to_parent_is_light(N,1); rep(v,N){ if (heavy_child[v]!=-1){ to_parent_is_light[heavy_child[v]] = 0; } } rep(v,N){ if (on_st_path[v]) to_parent_is_light[v] = 1; } vec,vec>> dp(N); auto dfs1 = [&](auto self,int v,int pv)->void { vector,vec>> child_polys; for (auto nv:edge[v]){ if (nv == parent[v] || on_st_path[nv]) continue; self(self,nv,v); if (nv!=heavy_child[v]){ child_polys.push_back(dp[nv]); dp[nv].first.clear(); dp[nv].second.clear(); } } dp[v] = merge_child(child_polys); if (to_parent_is_light[v]){ vector,vec>> path_polys = {dp[v]}; int pos = heavy_child[v]; while (pos!=-1 && !on_st_path[pos]){ path_polys.push_back(dp[pos]); pos = heavy_child[pos]; } dp[v] = merge_path(path_polys); } }; rep(v,N){ if (on_st_path[v]) dfs1(dfs1,v,-1); } vector,vec>> st_path_polys; vector> st_path_polys_non; { int pos = S; while (pos!=-1){ st_path_polys.push_back(dp[pos]); st_path_polys_non.push_back(dp[pos].first); pos = parent[pos]; } } //debug(st_path_polys); //debug(st_path_polys_non); vector q_det = merge_path(st_path_polys).second; vector p_det = calc_prod(st_path_polys_non); //debug(p_det); //debug(q_det); int D = int(st_path_polys.size()) - 1; if (M < D){ cout << 0 << "\n"; return ; } auto ans = BostanMori2(p_det,q_det,M-D); cout << ans << "\n"; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int T = 1; while (T--){ solve(); } }