頂点数の木が与えられます。個の頂点はそれぞれ番号からまでを用いて表せるものとします。
行にわたって、入力が与えられ、個目の入力では、頂点と頂点が辺で繋がれているということが伝えられます。
グラフが好きなモジャくんは木を見て、以下のことに気が付きました。
◉「異なる頂点を選択して、点の間に(元々辺が存在するかに関わらず)新しい辺を結ぶと、ちょうどつだけ閉路ができる。」
モジャくんは、気になってできる閉路の長さの期待値を考えましたが、他の課題が迫っている中、落ち着いて考えることができませんでした。
モジャくんの代わりに閉路の長さの期待値を求めてください。
なお、ここでの期待値は、考えうる全てののペア通りに対する、閉路の長さの平均値と解釈できます。
・
・
・与えられるグラフは木である。
・入力は全て整数値である。
N a_1 b_1 a_2 b_2 . . . a_(N-1) b_(N-1)
この問題の条件下では、求める期待値に対し
・
・
なる自然数のペアが一意に存在します。
を出力する代わりに、の範囲で一意に定まる、以上の自然数を出力してください。
最後に改行してください。
2 1 2
2
・です。より,となります。
5 1 2 2 3 5 4 2 4
399297744
・です。より,となります。
20 1 10 2 8 14 12 4 15 17 18 20 6 16 1 3 5 6 8 11 3 6 12 19 4 17 13 7 10 10 13 4 6 9 6 4 1 3 8
220664546
・です。より,となります。