問題一覧 > 通常問題

No.2587 Random Walk on Tree

レベル : / AI推定難易度 : 3250 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 10
作問者 : akakimidori / テスター : hos.lyric
お気に入りにしたユーザー ProblemId : 7938 / 自分の提出
問題文最終更新日: 2023-12-13 23:12:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2023 (順位表) の他の問題:

Problem Statement

You are given a tree $\mathcal{T}$ with $N$ vertices and $N-1$ edges. The vertices are numbered from $1$ to $N$, and the $i$-th edge connects vertices $A_i$ and $B_i$.

Given integers $M, S, T$, find the number, modulo $998244353$, of integer sequences $V = (V_0, V_1, \ldots, V_M)$ of length $M+1$ that satisfy all of the following 4 conditions.

  1. $1 \leq V_i \leq N$ ($0 \leq i \leq M$)
  2. $V_0 = S$
  3. $V_M = T$
  4. For every $i$ such that $1 \leq i \leq M$, either $V_{i- 1} = V_i$ or the tree $\mathcal{T}$ has an edge connecting vertices $V_{i - 1}$ and $V_i$.

Input

$N\ M\ S\ T$
$A_1\ B_1$
$\vdots$
$A_{N - 1}\ B_{N - 1}$

  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 10^9$
  • $1 \leq S, T \leq N$
  • $1 \leq A_i, B_i \leq N$
  • All input values are integers.
  • The given edges form a tree.

Output

Output the number of integer sequences modulo $998244353$. End the output with a newline.

Sample

Sample 1
Input
5 3 1 5
1 2
5 1
2 3
5 4
Output
6

The integer sequences satisfying the conditions are the following

  • $(1,1,1,5)$
  • $(1,1,5,5)$
  • $(1,2,1,5)$
  • $(1,5,1,5)$
  • $(1,5,4,5)$
  • $(1,5,5,5)$
for a total of $6$ sequences.

Sample 2
Input
6 2 2 3
3 5
1 6
4 2
5 4
6 5
Output
0

There may be no integer sequence satisfying the conditions.

Sample 3
Input
11 770250016 9 4
7 9
1 5
2 11
3 4
1 8
4 5
10 11
10 5
5 6
5 9
Output
231571356

Output the answer modulo $998244353$.

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