問題一覧 > 通常問題

No.1418 Sum of Sum of Subtree Size

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 147
作問者 : tada721 / テスター : hitonanode
11 ProblemId : 5860 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-06 20:03:52

問題文


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

入力

N
A1 B1
・
・
・
AN−1 BN−1

・2≤N≤100000=105
・1≤Ai,Bi≤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もしくは右上の雲マークをクリックしてアカウントを作成してください。