Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
1 から N までの番号のついた N 頂点からなる根付き木 T があります. 根は頂点 1 で,頂点 i (2 \leq i \leq N) の親は頂点 P_i (P_i<i) です. この木の辺は有向辺で,各辺は親から子の方向へ向いています.
あなたは T に M 本の辺を追加し,有向グラフ G を作りました. i 番目に追加した辺は,頂点 A_i から頂点 B_i へ向かう辺でした. ここで,A_i,B_i は以下の条件を満たすことが保証されます.
- 1 \leq B_i<A_i \leq N
- T において頂点 A_i は頂点 B_i の子孫である
- T において頂点 A_i は葉でない
なお,同じ辺を複数本追加することもありえます.
あなたはこれから G の頂点 1 からスタートし,停止するまで次の操作を繰り返します.
- 今いる頂点から出る辺が存在しないなら停止する.
- 今いる頂点から出る辺が存在するなら,そのうちの 1 つを一様ランダムに選び,その辺が向かう頂点へ移動する.
停止するまでに移動する回数の期待値を\pmod{P} で求めてください.
ただしこの問題では P の値は入力で与えられません. そのかわり,以下の制約をすべて満たすような P をあなたが選び,その P に対して問題を解いてください.
- P は素数
- 998244353 \leq P < 2 \times 10^9
- \pmod{P} で答えが定義できる
期待値 \pmod{P} の定義
求める期待値は必ず有理数になることが証明できます. その値を既約分数 \frac{P}{Q} で表した時,Q \neq 0 \pmod{P} となっていればこの値は\pmod{P} で定義できると言い,Q = 0 \pmod{P} ならば定義できないと言います.値が定義できる場合,R \times Q \equiv P \pmod{P}, 0 \leq R < P を満たす整数 R が一意に定まります. この R を答えてください.
この問題のジャッジについて
ジャッジはまず,あなたの選んだ P が最初の 2 つの条件を満たすかどうかチェックします. 条件を満たさない場合は,そのテストケースは不正解と判定します. 条件を満たす場合,ジャッジはこの P に対して問題を解くプログラムを実行します. ジャッジが答え\pmod{P} の値を計算できる場合,それをあなたの出力と比較して正誤判定を行います. ジャッジが答え\pmod{P} を計算できないが, 答えが\pmod{P} で定義できないと判断できる場合,そのテストケースは不正解と判定します. ジャッジが答え\pmod{P} を計算できず,かつ 答えが\pmod{P} で定義できるか否かが判断できない場合は,そのテストケースは正解と判定します. なお,この問題の制約下で,最初の 2 つの条件を満たす P のうち 99.9% 以上で期待値が定義でき,かつジャッジがそれを正しく計算できることが証明できます.
制約
- 2 \leq N \leq 250000
- 0 \leq M \leq 250000
- 1 \leq P_i < i
- 1 \leq B_i<A_i \leq N
- T において頂点 A_i は頂点 B_i の子孫である
- T において頂点 A_i は葉でない
- 入力される値はすべて整数
- サンプル以外のテストケースは 50 個以下である.
入力
入力は以下の形式で標準入力から与えられる.
N M P_2 P_3 \cdots P_N A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを以下の形式で出力せよ.
ans P
ここで P はあなたが選んだ素数であり,ans は\pmod{P} での答えである.
入力例 1
3 0 1 2
出力例 1
2 998244353
入力例 2
3 1 1 2 2 1
出力例 2
4 998244353
入力例 3
7 5 1 2 2 4 4 3 3 1 2 1 3 2 4 2 3 2
出力例 3
453747441 998244353
入力例 4
20 25 1 2 3 2 5 2 6 1 9 2 2 12 13 1 2 16 17 16 19 13 12 12 1 17 1 6 5 5 1 13 12 12 2 17 16 17 16 17 16 19 16 6 5 16 2 6 5 9 1 9 1 13 12 13 12 6 5 19 16 6 5 17 16 6 5 13 1 13 12
出力例 4
529789893 998244353