No.1418 Sum of Sum of Subtree Size
タグ : / 解いたユーザー数 152
作問者 :
tada721
/ テスター :
👑 
hitonanode
Problem Statement
You are given a tree with $N$ vertices.
The $i$-th edge connects vertices $A_i$ and $B_i$.
For a pair of integers $(x,y)$ satisfying $1 \le x,y \le N$, define $f(x,y)$ as follows.
・The size of the subtree rooted at vertex $y$ when vertex $x$ is the root
Find the sum of $f(x,y)$ over all pairs of integers $(x,y)$ satisfying $1 \le x,y \le N$.
Input
$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$
・The given graph is a tree
・All input values are integers
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 2 3
Output
17
$f(1,1)=3$ (the subtree contains vertices 1,2,3)
$f(1,2)=2$ (the subtree contains vertices 2,3)
$f(1,3)=1$ (the subtree contains vertex 3)
$f(2,1)=1$ (the subtree contains vertex 1)
$f(2,2)=3$ (the subtree contains vertices 1,2,3)
$f(2,3)=1$ (the subtree contains vertex 3)
$f(3,1)=1$ (the subtree contains vertex 1)
$f(3,2)=2$ (the subtree contains vertices 1,2)
$f(3,3)=3$ (the subtree contains vertices 1,2,3)
Therefore, the answer is 3+2+1+1+3+1+1+2+3=17.
Sample 2
Input
5 1 2 2 3 3 4 3 5
Output
61
Sample 3
Input
10 1 2 1 3 1 5 1 7 3 6 3 8 4 7 5 9 8 10
Output
334
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。