分数: 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