Distance Sums 2

题目描述

给出一棵有 $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$ 必须经过的最少边数。

输入格式

输入按照下面的格式从标准输入给出： $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)$。

3
1 2
2 3

3
2
3

2
1 2

1
1

6
1 6
1 5
1 3
1 4
1 2

5
9
9
9
9
9

提示

$2 \leq N \leq 2 \times 10^5$ 1 \leq u_i < v_i \leq N 给定的图是一棵树。 输入中的所有数值均为整数。我们有： $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$.

标签: AtCoder|abc220F

来源

AtCoder|abc220F