問題一覧 > 通常問題

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

レベル : / AI推定難易度 : 2450 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 13
作問者 : 👑 Kazun / テスター : square1001
お気に入りにしたユーザー ProblemId : 8628 / 自分の提出
問題文最終更新日: 2023-05-19 20:44:26
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
yukicoder contest 389 (Until that day when "Cherry Month" is over.) (順位表) の他の問題:

Story

"Even if we say goodbye here, we'll surely meet again somewhere, won't we?"

Problem Statement

There is a rooted tree with $(N+1)$ vertices. The $(N+1)$ vertices are numbered $0,1,2,\dots,N$. The root is vertex $0$, and the parent of vertex $i~(1 \leq i \leq N)$ is vertex $P_i~(0 \leq P_i \lt i)$.

Cherry is initially at vertex $0$.

Cherry moves between vertices some number of times according to the following rules.

  • If the vertex Cherry is at is not a leaf: she moves to one of the children of that vertex. The destination is chosen with probability proportional to $W_i$.
    • Formally, when the children of that vertex are $u_1, u_2, \dots, u_l$, the probability that $u_i$ is chosen as the next destination is $\dfrac{W_{u_i}}{W_{u_1}+W_{u_2}+\dots+W_{u_l}}$.
    The choice of destination in this case is independent for each move.
  • If the vertex Cherry is at is a leaf: she moves to the root (vertex $0$).

Answer the following $Q$ queries $q~(1 \leq q \leq Q)$.

  • Query $q$ : Let $E$ be the expected number of times vertex $A_q$ is chosen as the destination when Cherry performs the above move $K_q$ times. Find $E \pmod{998244353}$.

Notes

Under the constraints of this problem, for $E$ in each query, $X \times E=Y$ holds for some integer that is not a multiple of $998244353$, namely $X$, and some integer $Y$.

For these $X,Y$, there exists a unique integer with $X \times Z \equiv Y \pmod{998244353}$ that is at least $0$ and less than $998244353$, namely $Z$. Using this $Z$, we define $E \pmod{998244353}:=Z$.

Note that many pairs satisfying $X \times E =Y$ can be considered, consisting of an integer that is not a multiple of $998244353$, namely $X$, and an integer $Y$; however, $Z$ does not depend on the choice of $X,Y$ and is determined only by $E$.

Constraints

  • $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)$.
  • All input values are integers.

Input

The input is given from standard input in the following format.
$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$

Output

The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print the answer to query $q$ as an integer on $1$ line.

Do not forget the newline at the end.

Sample

Sample 1
Input
3
0 0 2
1 2 3
4
0 3
1 3
2 3
3 3
Output
1
776412275
554580197
665496236

The possible ways Cherry can move are as follows.

  • Vertex $0$ $\to$ vertex $1$ $\to$ vertex $0$ $\to$ vertex $1$ : probability $\frac{1}{9}$
  • Vertex $0$ $\to$ vertex $1$ $\to$ vertex $0$ $\to$ vertex $2$ : probability $\frac{2}{9}$
  • Vertex $0$ $\to$ vertex $2$ $\to$ vertex $3$ $\to$ vertex $0$ : probability $\frac{2}{3}$
Therefore, $E_0=1, E_1=\dfrac{4}{9}, E_2=\dfrac{8}{9}, E_3=\dfrac{2}{3}$. Note that the initial position at vertex $0$ is not counted.

Also, for example, $9 \times E_1=4$ and $9 \times 776412275 \equiv 4 \pmod{998244353}$, so $E_1 \pmod{998244353}=776412275$.

Sample 2
Input
1
0
46
4
0 46
1 46
0 0
1 0
Output
23
23
0
0

Cherry goes back and forth between vertex $0$ and vertex $1$.

Sample 3
Input
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
Output
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$ are not necessarily in ascending order and may contain duplicates.

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