問題一覧 > 通常問題

No.2587 Random Walk on Tree

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 9
作問者 : akakimidori / テスター : 👑 hos.lyric
4 ProblemId : 7938 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-13 23:12:56

問題文

NN 頂点 N−1N-1 辺の木 T\mathcal{T} が与えられます。 頂点には 11 から NN までの番号がついており、ii 番目の辺は頂点 AiA_i と頂点 BiB_i を結んでいます。

整数 M,S,TM, S, T が与えられるので以下の4つの条件を全て満たす長さ M+1M+1 の整数列 V=(V0,V1,…,VM)V = (V_0, V_1, \ldots, V_M) の個数を 998244353998244353 で割ったあまりを求めてください。

  1. 1≤Vi≤N1 \leq V_i \leq N (0≤i≤M0 \leq i \leq M)
  2. V0=SV_0 = S
  3. VM=TV_M = T
  4. 1≤i≤M1 \leq i \leq M となる全ての ii について Vi−1=ViV_{i- 1} = V_i または木 T\mathcal{T} で頂点 Vi−1V_{i - 1} と頂点 ViV_i を結ぶ辺が存在する。

入力

N M S TN\ M\ S\ T
A1 B1A_1\ B_1
⋮\vdots
AN−1 BN−1A_{N - 1}\ B_{N - 1}

  • 1≤N≤1051 \leq N \leq 10^5
  • 1≤M≤1091 \leq M \leq 10^9
  • 1≤S,T≤N1 \leq S, T \leq N
  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
  • 入力はすべて整数
  • 与えられる辺は木をなす

出力

整数列の個数を 998244353998244353 で割ったあまりを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
5 3 1 5
1 2
5 1
2 3
5 4
出力
6

条件を満たす整数列として

  • (1,1,1,5)(1,1,1,5)
  • (1,1,5,5)(1,1,5,5)
  • (1,2,1,5)(1,2,1,5)
  • (1,5,1,5)(1,5,1,5)
  • (1,5,4,5)(1,5,4,5)
  • (1,5,5,5)(1,5,5,5)
の 66 通りがあります。

サンプル2
入力
6 2 2 3
3 5
1 6
4 2
5 4
6 5
出力
0

条件を満たす整数列が存在しない時もあります。

サンプル3
入力
11 770250016 9 4
7 9
1 5
2 11
3 4
1 8
4 5
10 11
10 5
5 6
5 9
出力
231571356

998244353998244353 で割ったあまりを出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。