No.1418 Sum of Sum of Subtree Size
タグ : / 解いたユーザー数 146
作問者 :
tada721
/ テスター :
hitonanode
問題文
$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もしくは右上の雲マークをクリックしてアカウントを作成してください。