問題一覧 > 通常問題

No.1418 Sum of Sum of Subtree Size

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 110
作問者 : tada721tada721 / テスター : 👑 hitonanodehitonanode
10 ProblemId : 5860 / 出題時の順位表
問題文最終更新日: 2021-02-06 20:03:52

問題文


$N$頂点からなる木が与えられます。
$i$番目の辺は頂点$A_i$と$B_i$を結んでいます。
ここで、$1 \le x,y \le N$を満たす整数の組$(x,y)$に対し、$f(x,y)$を次のように定義します。
・頂点$x$を根とした時の頂点$y$を根とする部分木のサイズ
$1 \le x,y \le N$を満たす全ての整数の組$(x,y)$についての$f(x,y)$の総和を求めてください。

入力

$N$
$A_1$ $B_1$
・
・
・
$A_N$$_-$$_1$ $B_N$$_-$$_1$

・$2 \le N \le 100000=10^5$
・$1 \le A_i, B_i \le N$
・与えられるグラフは木
・入力は全て整数である

出力

答えを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
1 2
2 3
出力
17


$f(1,1)=3$(部分木に含まれるのは頂点1,2,3)
$f(1,2)=2$(部分木に含まれるのは頂点2,3)
$f(1,3)=1$(部分木に含まれるのは頂点3)
$f(2,1)=1$(部分木に含まれるのは頂点1)
$f(2,2)=3$(部分木に含まれるのは頂点1,2,3)
$f(2,3)=1$(部分木に含まれるのは頂点3)
$f(3,1)=1$(部分木に含まれるのは頂点1)
$f(3,2)=2$(部分木に含まれるのは頂点1,2)
$f(3,3)=3$(部分木に含まれるのは頂点1,2,3)
よって答えは3+2+1+1+3+1+1+2+3=17です。

サンプル2
入力
5
1 2
2 3
3 4
3 5
出力
61

サンプル3
入力
10
1 2
1 3
1 5
1 7
3 6
3 8
4 7
5 9
8 10
出力
334

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。