F - Distance Sums 2

Contest Duration: 2021-09-26(Sun) 12:00 - 2021-09-26(Sun) 13:40 (local time) (100 minutes) Back to Home

F - Distance Sums 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $500$ 点

問題文

$N$ 頂点の木が与えられます。頂点には $1,2,\ldots ,N$ の番号がついており、 $i$ 番目の辺は頂点 $u_i,v_i$ を結ぶ無向辺です。

各整数 $i\,(1 \leq i \leq 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)$ を出力せよ。

入力例 1Copy

Copy

3
1 2
2 3

出力例 1Copy

Copy

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$ 、

です。

入力例 2Copy

Copy

2
1 2

出力例 2Copy

Copy

1
1

入力例 3Copy

Copy

出力例 3Copy

Copy

Score : $500$ points

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 1Copy

Copy

3
1 2
2 3

Sample Output 1Copy

Copy

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 2Copy

Copy

2
1 2

Sample Output 2Copy

Copy

1
1

Sample Input 3Copy

Copy

Sample Output 3Copy

Copy