Sailing Distance Sum in Island Reunion

This problem is about computing the sum of sailing distances from every other island to each candidate island in a connected network of islands. In the context of a sailing regatta, the organizers are considering each island as a possible venue. They wonder: if every other island sends one sailboat, what is the minimum number of jumps required to gather all boats at the candidate island? Equivalently, what is the sum of the sailing distances (in number of hops) from all other islands to that island?

You are given a tree (i.e. a connected graph with no cycles) with N islands numbered from 1 to N. For each island K, compute the following sum: \[ S(K)=\sum_{\substack{i=1\\ i\neq K}}^{N} d(i,K), \] where \(d(i,K)\) is the minimum number of hops (edges) between island i and island K.

The input is guaranteed to satisfy that for every pair of islands, there is a sequence of jumps connecting them.

Note: All formulas are provided in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(N\) (\(2 \leq N \leq 10^5\)), the number of islands. Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) representing an undirected edge (a direct sailing connection) between islands \(u\) and \(v\).

outputFormat

Print a single line containing \(N\) integers where the \(k\)-th integer is the sum of the minimum sailing distances (in hops) from all other islands to island \(k\).

sample

4
1 2
1 3
3 4

4 6 4 6