Everyone's Total Commute

Difficulty: 2100 6000 ms 128 MB

dp trees rerooting

For EVERY node v, print the sum of distances from v to all other nodes — N answers, one per line.

Input: the first line has N; the next N−1 lines have the edges.

Output: N lines: the distance sum for nodes 1..N.

Constraints:

• 1 ≤ N ≤ 5×10⁴

Sample Tests

4
1 2
1 3
3 4

4
6
4
6

1

0

Read the Editorial