← 返回题目列表

AtCoder · abc220_f

I. 距离总和 2

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给定的是一棵树 N 顶点。顶点已编号 1,2,\ldots ,N,以及 i-th 边是连接顶点的无向边 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).


样本输入 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