遷移を表す行列 \(A\) を作ります． 具体的には \(A[i][j]=\) 頂点 \(i\) から頂点 \(j\) に遷移する確率とします．

各頂点 \(i\) に対し \(i\) からスタートした場合の移動回数の期待値を \(x_i\) とおき，長さ \(N\) の(縦)ベクトル \(x=(x_1,x_2,\cdots,x_N)\) を定義します．

また，長さ \(N\) の(縦)ベクトル \(t=(t_1,t_2,\cdots,t_N)\) を，次のように定義します．

• 頂点 \(i\) から出る辺が存在する場合 \(t_i=1\)
• 頂点 \(i\) から出る辺が存在しない場合 \(t_i=0\)

ここで，遷移の様子から \(Ax+t=x\) という等式が成立します． これを変形すれば，\((I-A)x=t\) という等式が得られます． ただしここで \(I\) は単位行列です．

上の等式を解き，\(x_1\) の値を求められればよいです． まず，\(I-A\) が可逆であることが証明できます． これは Absorbing Markov Chain の典型的な結果です．

\(x\) が一意に定まることがわかりましたが，愚直に \(1\) 次方程式を解くととても間に合いません．

そこでクラメルの公式を使います． \(B=I-A\) とおき，さらに \(B\) の \(1\) 列目を \(t\) で置き換えた行列を \(B'\) とすると，\(x_1=\det(B')/\det(B)\) と求まります． あとは \(\det(B)\) を求められればよいです．(\(\det(B')\) も同じ方法で解けます)

\(\det\) の定義に立ち返ると，頂点をいくつかの有向サイクルに分割し，適切な係数を書けた和を取る，という計算ができればよいです．

\(B\) の定義を見ると，これはもとの問題文で与えられたグラフ \(G\) に自己ループが追加されたような形をしています． このようなグラフにおけるサイクルは，自己ループであるか，後退辺を \(1\) 本だけ使うようなサイクルです．

ここまでわかればあとは木DPが行えます． 各部分木について，その部分木内だけ見たときの行列式を計算すればよいです． 遷移の計算方法は，大別すると\(2\) 通りありますが(いわゆる”送るDP”と”受け取るDP”)，結局のところ，パス上の和を取ったり部分木内の値を全部定数倍したりといった操作に帰着され，データ構造で処理することができます．

以上を実装すれば，全体の計算量 \(O((N+M)\log(N+M))\) でこの問題を解くことができます．

回答例(C++)

\(\pmod{P}\) で動作する確率についてのメモ：

\(0\) 割が発生する可能性があるのは，\(\det(B) \equiv 0 \pmod P\) となる場合のみです． \(\det(B)\) について検証します． \(B\) の各行 \(i\) を，\(i\) の出次数で定数倍すると \(B\) は整数成分のみの行列になります．この行列を \(C\) とおくことにします． ここで，\(C\) の各成分の絶対値の和は \(2(N+M) \leq 10^6\) 以下です． ここから \(\det(C)\) の絶対値は高々 \(3^{10^6/3}\) (程度)と見積もることができます． すると，\(\det(C)\) が持つ \(998244353\) 以上の素因数は高々 \(18000\) 個と見積もれます． 問題文中の条件を満たす \(P\) は \(47459422\) 個あるので，\(99.9\) % 以上の \(P\) で \(\det(C) \not \equiv 0 \pmod P\) となることが示されました．