No.2587 Random Walk on Tree
タグ : / 解いたユーザー数 10
作問者 :
akakimidori
/ テスター :
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 \leq V_i \leq N$ ($0 \leq i \leq M$)
- $V_0 = S$
- $V_M = T$
- 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)$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。