問題一覧 > 通常問題

No.2305 [Cherry 5th Tune N] Until That Day...

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 14
作問者 : KazunKazun / テスター : square1001square1001
1 ProblemId : 8628 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-19 20:44:26

ストーリー

「ここでサヨナラしても, またどこかできっと会えるよね?」

問題文

$(N+1)$ 頂点からなる根付き木がある. $(N+1)$ 個の頂点は $0,1,2,\dots,N$ と番号付けられている. 根は頂点 $0$ であり, 頂点 $i~(1 \leq i \leq N)$ の親は頂点 $P_i~(0 \leq P_i \lt i)$ である.

チェリーちゃんは最初, 頂点 $0$ にいる.

チェリーちゃんは以下のルールに従って, 頂点の移動を何回か行う.

  • チェリーちゃんがいる頂点が葉ではない場合: その頂点の子のいずれかに移動する. 移動先は $W_i$ に比例する確率で選ばれる.
    • 厳密には, その頂点の子が $u_1, u_2, \dots, u_l$ であるとき, $u_i$ が次の移動先として選ばれる確率は $\dfrac{W_{u_i}}{W_{u_1}+W_{u_2}+\dots+W_{u_l}}$ である.
    また, この場合における移動先の選択については各移動毎に独立であるとする.
  • チェリーちゃんがいる頂点が葉である場合: 根 (頂点 $0$) に移動する.

このとき, 以下の $Q$ 個の質問 $q~(1 \leq q \leq Q)$ に答えよ.

  • 質問 $q$ : チェリーちゃんが上記の移動を $K_q$ 回行った際, 頂点 $A_q$ が移動先として選ばれる回数の期待値を $E$ とする. このとき, $E \pmod{998244353}$ を求めよ.

注記

この問題の制約下においては, 各質問における $E$ に対して, $X \times E=Y$ となる $998244353$ の倍数ではない整数 $X$ と整数 $Y$ が存在する.

この $X,Y$ に対して, $X \times Z \equiv Y \pmod{998244353}$ となる $0$ 以上 $998244353$ 未満の整数 $Z$ が唯一存在するので, この $Z$ を用いて, $E \pmod{998244353}:=Z$ とする.

なお, $X \times E =Y$ となる $998244353$ の倍数ではない整数 $X$ と整数 $Y$ は数多に考えられるが, $Z$ は $X,Y$ の取り方によらず, $E$ にのみによって決まる.

制約

  • $1 \leq N \leq 5000$.
  • $0 \leq P_i \lt i \quad (0 \leq i \leq N)$.
  • $1 \leq W_i \leq 10^5 \quad (0 \leq i \leq N)$.
  • $1 \leq Q \leq 20$.
  • $0 \leq A_q \leq N \quad (1 \leq q \leq Q)$.
  • $0 \leq K_q \leq 10^9 \quad (1 \leq q \leq Q)$.
  • 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる. 
$N$
$P_1$ $P_2$ $\dots$ $P_N$
$W_1$ $W_2$ $\dots$ $W_N$
$Q$
$A_1$ $K_1$
$A_2$ $K_2$
$\vdots$
$A_Q$ $K_Q$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には, 質問 $q$ に対する解答を整数で $1$ 行に出力せよ.

最後に改行を忘れないこと.

サンプル

サンプル1
入力
3
0 0 2
1 2 3
4
0 3
1 3
2 3
3 3
出力
1
776412275
554580197
665496236

実現するチェリーちゃんの移動の方法として次のようなものがある.

  • 頂点 $0$ $\to$ 頂点 $1$ $\to$ 頂点 $0$ $\to$ 頂点 $1$ : 確率 $\frac{1}{9}$
  • 頂点 $0$ $\to$ 頂点 $1$ $\to$ 頂点 $0$ $\to$ 頂点 $2$ : 確率 $\frac{2}{9}$
  • 頂点 $0$ $\to$ 頂点 $2$ $\to$ 頂点 $3$ $\to$ 頂点 $0$ : 確率 $\frac{2}{3}$
よって, $E_0=1, E_1=\dfrac{4}{9}, E_2=\dfrac{8}{9}, E_3=\dfrac{2}{3}$ である. 最初にいる頂点 $0$ はカウントしないことに注意せよ.

また, 例えば, $9 \times E_1=4$ であり, $9 \times 776412275 \equiv 4 \pmod{998244353}$ であるから, $E_1 \pmod{998244353}=776412275$ である.

サンプル2
入力
1
0
46
4
0 46
1 46
0 0
1 0
出力
23
23
0
0

チェリーちゃんは頂点 $0$ と頂点 $1$ を往復する.

サンプル3
入力
15
0 1 2 2 3 1 4 6 8 9 1 11 8 10 7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20
0 20150821
1 20160406
2 20160810
3 20161130
4 20170405
10 20170719
5 20171025
6 20180307
7 20180815
8 20190227
11 20200821
12 20201007
0 20201014
1 20201209
2 20210414
3 20211013
4 20220406
13 20220803
14 20221108
15 20221109
出力
984593583
66562935
853150486
450394280
487556810
425770516
164383442
737722434
878250685
64190509
176934106
581447838
504103921
609099868
775475173
525420298
255941538
712197622
537846225
240794030

$A_1, \dots, A_M$ は昇順とは限らないうえに, 重複があるかもしれない.

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