Description
Problem brought to you by NTHU Amusement Programming Club.
After being kicked out of NTHU due to lack of talents in programming, GY Lin had no choice but to start living in a tree (a connected, acyclic graph). If you fail this course, you will meet the same fate.
Knowing this, his friend and tutor Shepherd comes to visit GY. Unfortunately for him, GY is not at home, but he doesn’t realized this until he has already traversed every node. During that, he discovered something interesting: when he steps onto a node, the view may change dramatically.
The tree has N nodes, and nodes are numbered distinctly from 1 to N. The view from a node u can be quantified as a single integer val(u), which can be obtained using the following algorithm:
set root := u
set val(root) := 0
set boolean array vis[i]:=false for i=1...N
call dfs(root,0)
The dfs algorithm is defined as follows:
dfs(v, lv):
set vis[v] := true
val(root) := val(root) + lv
for any neighbor w of v
if vis[w]=false:
call dfs(w,lv+1)
Now that Shepherd has already traversed the whole tree, he wonders what is the sum of view of every node.
Input
There is only one testcase per input file, each describing the structure of a tree.
On the first line, there is a single integer N, which is the number of nodes; N−1 lines follow, each containing two integers u v, meaning there is an edge between node u and v.
1 <= N <= 2*105
Output
Output a single integer that is the sum of val(u) for u=1...N.