この解説では計算で \(0\) 除算が出てくる確率は評価していません．この解法でのその確率が公式解説と同じであるかも検証していません．

\(X[v]\) を，頂点 \(X[v]\) から出ていく各辺を通る移動回数の期待値とします（これは \(v\) のみから定まり辺には依存しません）．また \(v\) の出次数を\(n_v\) とします.

葉では \(X[v]=0\) で，それ以外は，出て行く回数と入ってくる回数の釣り合いを考えると \(v\) の親を \(p\) として \(n_vX[v]=X[p]+\sum X[w]\) という式になります．ただし \(v\) が根のときは \(X[p]=1\) とします．また，\(\sum\) は後退辺 \(wv\) をわたります．

この式を使うと，葉側から順に，\(X[v]=c_vX[p]\) となる \(c_v\) が定まることが帰納的に分かります．部分木内の \(v\) 以外の点で \(c\) が求まっているとして \(X[w]\) と \(X[v]\) の比は，パス上の値から求まるからです．

この議論はそのまま解法になります．\(O(N+M\log N)\) 時間などの計算量で解けます．

解答例 https://atcoder.jp/contests/jsc2024-final/submissions/56988735