まずスコアが \(0\) でない確率を求めてみます．

実数だと分かりづらいので，離散的な問題を考えます． 整数 \(M\) に対して，各頂点に \([-(N-1)\times M,M]\) の値を書き込んで，\(0 \leq x_i \leq M\) を満たす確率を求める，という問題を考えます．

各頂点に値を書き込んだあと，\(x_i\) が同じ隣接頂点を \(1\) つのグループにまとめたとします．

今，\(K\) 個のグループ \(C_1,\cdots,C_K\) と，そこでの \(x_i\) の値 \(y_1,\cdots,y_K\) を一つ固定したとします． ここで，\(y_i\) はすべて distinct であることを仮定します．

この状態を達成する値の書き込み方の個数は，次の値になります．

• \(\prod_{1 \leq i \leq K} (y_i+1)^{|C_i|-1}\)

これは次のようにわかります．

まず \(y_i\) が最大となるグループ \(C_i\) を考えます． このグループに対応する部分木を取り出し，適当な頂点を根にして \(T_i\) とおきます． 各辺について，そこの下の部分木の値の総和は \([0,y_i]\) であるべきで，かつその範囲ならば好きに選んで良いです． そして，この選択をすべての辺について独立に行うことができます． 最後に部分木全体の値の総和が \(y_i\) になることを踏まえると，この部分木で \(y_i\) を達成するような値の書き方の個数は \((y_i+1)^{|C_i|-1}\) となります．

\(y_i\) が最大でない場合も似たように考えることができます． このグループ内の適当な頂点 \(v\) について，それに隣接するグループ \(C_j\) の値 \(y_j\) が \(y_i\) より大きかったとします． ここで，\(v\) を含む部分木が \(x_v\) を達成するときは，必ず \(C_j\) をすべて含んでいることがわかります． すると結局，\(y_j\) は頂点 \(v\) の値の offset と捉えることができます． あと先ほどと全く同じ議論で，\(T_i\) の値が \(y_i\) になるような値の書き方の個数は \((y_i+1)^{|C_i|-1}\) となります．

この考察を元に，問題を \([0,1]\) 実数に戻してやると，以下のような問題になります．

• 木をいくつかの部分木に分解する方法をすべて試す．
• 各部分木について，その頂点数を \(c\) とすると \(\int_{0}^{1} x^{c-1} = 1/c\) の重みがかかる
• 重みの総積をすべての方法について足し合わせよ．

ここではスコアを勘定に入れていませんが，これは単に重みを \(\int_{0}^{1} x^c \times x^{c-1} = 1/(2c)\) にするだけの違いです．

あとはこの問題を解けばよく，これは典型的な木 DP で \(O(N^2)\) 時間で解けます．

回答例(C++)