Total Depth

Difficulty: 1300 4000 ms 128 MB

trees

Rooted at node 1, print the sum of the depths of all nodes (the root has depth 0).

Input: the first line has N; each of the next N−1 lines has an edge u v.

Output: the sum of all node depths.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

4
1 2
2 3
2 4

5

1

0

Read the Editorial