DistTree

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 500M

Authors:

luismo, frankr, eliogovea

Problem type

Allowed languages

Ada, Brain****, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, ~~Swift~~, VB

Given a tree, it is wanted to know for each node the sum of the distances from it to the remaining ones.

Input

A line containing a single integer $N$ ~N~ ( $N \le 100000$ ~N \le 100000~), the amount of nodes in the tree. $N - 1$ ~N - 1~ lines representing the edges of the tree.

Output

$N$ ~N~ lineas, the ith line must contain the sum of the distances from all nodes to the $i-th$ ~i-th~ one.

Input Sample

3
1 2
2 3

Output Sample

3
2
3

Comments

0

LeandroGamer commented on Sept. 24, 2025, 4:08 a.m.

Alguna idea?

0

juan_alejandro commented on Sept. 24, 2025, 12:34 p.m.

Usa DP de re-rooting