C: Fractal Tree
問題
AORイカちゃんは、フラクタルな(自己相似的な)構造を持つ根付き木が好きである。 $N$ 頂点から成る重み付き根付き木 $T$ を用いて、以下のようなフラクタル構造を持つ根付き木 $T'$ を表現することを考える。
- $T'$ は、$T$ の各頂点 $x$ に対して、$x$ を根として $T$ と同様の木構造 (コストも同じ) を持つ木を付け加えたものである。
- $T'$の根は $T$ のものと同じものである。
こうして表現される木は例えば下図のようになる。
AOR イカちゃんは、$T'$ に対して深さ優先探索をしようとしているが、全ての頂点を辿ると時間がとてもかかることに気づいた。 そこで、深さ優先探索時の遷移の際に確率 $p$ で遷移し、確率 $1-p$ で遷移しない方針で深さ優先探索を行い、いくつかのノード訪問をサボることにした。 $T$ と確率 $p$ が与えられるので、$T’$ に対して深さ優先探索を行う際に辿る全ての辺のコストの和の期待値を求めよ。 $T$ の情報は頂点数 $N$ と $N-1$ 本の辺の情報で与えられ、頂点 $1$ が根である。 各頂点は $1,2,\dots,N$ とラベリングされており、 $i \ (1 \le i \le N-1)$ 番目の辺は頂点 $x_i$ と $y_i$ をコスト $c_i$ で結んでいる。 今回の問題で扱う、確率 $p$ で子に遷移する深さ優先探索の非決定的アルゴリズムは以下のように表現される。 出力される $\mathrm{answer}$ が辿る辺のコストの総和である。
- 空のスタック $S$ を用意する。
- $\mathrm{answer}=0$ とする
- $S$ に $T'$ の根頂点をプッシュする。
- $S$ の先頭の要素を取り出し、これを $x$ とする。
- $x$ の各子 $c$ に対し、それぞれ確率 $p$ で次の操作を行い、確率 $1-p$ で何もしない。
- $S$ に頂点 $c$ を追加する。そして $\mathrm{answer}$ に $x$ から $c$ に繋がっている辺の重みを加える。
- Sが空でなければ、3. に遷移する。
- $\mathrm{answer}$ を出力する。
制約
- $2 \le N \le 10^5$
- $0 \le p \le 1.0$ (小数点第 2 位まで与えられる。)
- $1 \le x_i,y_i \le N$
- $1 \le c_i \le 1000$
- $c_i$ は整数である
- 与えられるグラフは $N$ 頂点の根付き木である。すなわち、頂点 $N$、辺数 $N-1$、連結という性質を持つグラフであり、頂点 $1$ が根である。
入力形式
入力は以下の形式で与えられる。
$p$
$N$
$x_1 \ y_1 \ c_1$
$\vdots$
$x_{N-1} \ y_{N-1} \ c_{N-1}$
出力
答えを 1 行で出力せよ。相対誤差または絶対誤差が $10^{-6}$ 以下なら AC となる。また、末尾に改行も出力せよ。
サンプル
サンプル入力1
0.75 4 1 2 1 2 3 3 3 4 10
サンプル出力1
24.8569335938
サンプル入力2
0.75 4 1 2 1 1 3 3 3 4 10
サンプル出力2
35.0390625
問題文の図の木を与える例である。