0023 - Is It Bipartite Graph?

Problem

問題

$N$頂点の木があり、各頂点には$1$から$N$の番号がついている。$i$番目の辺は頂点$a_i$と$b_i$を結んでいる。
整数$x$, $y$を$[1, N]$の一様乱数で生成し、この木に頂点$x$と$y$を繋ぐ辺を追加するとする。
このグラフが2部グラフになる確率を$D$とした時、$N^2D/2$を求めなさい。
ただし、この制約下で$N^2D/2$が整数になることは証明できる。

入力

$N$
$a_1$ $b_1$ 
$a_2$ $b_2$ 

:

$a_{N-1}$ $b_{N-1}$ 

出力

$N^2D$を1行に出力しなさい。

制約

$1\leq N\leq10^5$
$1\leq a_i, b_i\leq N$

小課題

小課題 Small $[$ $50$ 点 $]$
・$N\leq300$

小課題 Large $[$ $100$ 点 $]$
・$N\leq3000$

小課題 Euglena $[$ $250$ 点 $]$
・追加の制約はない。

サンプルケース

入力例1

3
2 1
3 1

出力例1

2
$x=1, y=2$、$x=1, y=3$、$x=2, y=1$、$x=3, y=1$の場合だけ2部グラフになる。
辺を追加した後に二重辺があっても良いことに注意。

入力例2

1

出力例2

0

入力例3

15
14 1
5 9
8 13
7 10
2 7
5 4
4 1
8 4
9 12
11 2
12 15
3 1
4 6
1 2

出力例3

56