102205: [AtCoder]ABC220 F - Distance Sums 2

Problem Statement

Given is a tree with $N$ vertices. The vertices are numbered $1,2,\ldots ,N$, and the $i$-th edge is an undirected edge connecting Vertices $u_i$ and $v_i$.

For each integer $i\,(1 \leq i \leq N)$, find $\sum_{j=1}^{N}dis(i,j)$.

Here, $dis(i,j)$ denotes the minimum number of edges that must be traversed to go from Vertex $i$ to Vertex $j$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• The given graph is a tree.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

Output

Print $N$ lines.

The $i$-th line should contain $\sum_{j=1}^{N}dis(i,j)$.

Sample Input 1

3
1 2
2 3

Sample Output 1

3
2
3

We have:

$dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3$,

$dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2$,

$dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3$.

Sample Input 2

2
1 2

Sample Output 2

1
1

Sample Input 3

6
1 6
1 5
1 3
1 4
1 2

Sample Output 3

5
9
9
9
9
9

问题描述

给定一个包含N个顶点的树。顶点编号为1,2,……,N，第i条边是一个连接顶点u_i和顶点v_i的无向边。

对于每个整数i(1≤i≤N)，求$\sum_{j=1}^{N}dis(i,j)$。

其中，$dis(i,j)$表示从顶点i到顶点j所需的最少边的数量。

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入从标准输入按以下格式给出：

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出

输出N行。

第i行应包含$\sum_{j=1}^{N}dis(i,j)$。

样例输入1

3
1 2
2 3

样例输出1

3
2
3

我们有：

$dis(1,1)+dis(1,2)+dis(1,3)=0+1+2=3$，

$dis(2,1)+dis(2,2)+dis(2,3)=1+0+1=2$，

$dis(3,1)+dis(3,2)+dis(3,3)=2+1+0=3$。

样例输入2

2
1 2

样例输出2

1
1

样例输入3

6
1 6
1 5
1 3
1 4
1 2

样例输出3

5
9
9
9
9
9