頂点に $1$ から $N$ の番号がついた $N$ 頂点の根付き木が与えられます。 根は頂点 $1$ であり、$i=2,\ldots,N$ に対して頂点 $i$ の親は頂点 $A_i$ です。 また、各頂点 $i$ は重み $W_i$ を持っています。
クエリが $Q$ 個与えられるので、順に処理してください。各クエリは以下の2種類です。
1 x w の形式で与えられる。 頂点 $x$ の重み $W_x$ を $w$ で更新する。2 x の形式で与えられる。 頂点 $x$ を根とする部分根付き木に含まれる頂点集合から、各頂点の重みに比例する確率で独立に頂点を2つ選ぶ。 選ばれた $2$ 頂点の最近共通祖先の深さの期待値を $\bmod\ 998244353$ で出力する。ここで、選んだ $2$ つの頂点が同一である可能性があることに注意せよ。ある頂点 $v$ の深さは、 各辺の長さを $1$ としたときの根 (頂点 $1$) から $v$ までの最短距離で定義されます。
期待値 $\bmod\ 998244353$ とは
求める期待値は必ず有理数になります。
また、この問題の制約のもとでは、その値を既約分数 $P/S$ で表したとき、 $S\not\equiv 0 \bmod\ 998244353$ となります。
よって、 $R\times S \equiv P \bmod\ 998244353, 0\leq R < 998244353$ を満たす整数 $R$ が一意に定まります。
この $R$ を求めてください。
入力は以下の形式で標準入力から与えられます。
$N$ $Q$ $A_2$ $A_3$ $\ldots$ $A_N$ $W_1$ $W_2$ $\ldots$ $W_N$ $query_1$ $query_2$ $\vdots$ $query_Q$
ただし、 $query_i$ は $i$ 個目のクエリを表し、以下のいずれかの形式で与えられます。
1 $x$ $w$
2 $x$
種類 $2$ のクエリの個数を $q$ として、 $q$ 行出力してください。 $i$ 行目には、 $i$ 個目の種類 $2$ のクエリに対する答えを出力してください。
4 4 1 1 2 5 10 6 5 2 1 2 2 1 2 8 2 1
38394014 443664158 377807759
$1$ つ目のクエリについて、頂点 $1$ を根とする部分根付き木の重さの総和は $26$ です。 最近共通祖先の深さについて、
よって、求める期待値は $\frac{10^2+6^2+10\cdot 5+5\cdot 10}{26^2}\cdot 1+\frac{5^2}{26^2}\cdot 2=11/26$ となり、 $\bmod\ 998244353$ で表すと $38394014$ になります。