AT_abc220_f [ABC220F] 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)$ 的值。

输入输出样例 #1

输入 #1

3
1 2
2 3

输出 #1

3
2
3

输入输出样例 #2

输入 #2

2
1 2

输出 #2

1
1

输入输出样例 #3

输入 #3

6
1 6
1 5
1 3
1 4
1 2

输出 #3

5
9
9
9
9
9

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq u_i < v_i \leq N$
• 给定的图为一棵树
• 输入均为整数

样例解释 1

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

由 ChatGPT 4.1 翻译