← 返回题目列表

AtCoder · arc215_f

F. 肩胛骨

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

分数: 700 点

问题陈述

你有一棵树 N 顶点编号 1 to N。的 i第边缘 (1 \le i \le N - 1) 连接顶点 A_i 和 B_i。 对于该树中的路径,将路径的分数定义为从路径到最远顶点的距离。 这里,距路径的距离被定义为到路径上的顶点的最小距离。

得分最低的路径称为好路径。

对于每个 k = 1, 2, \ldots, N,精确找到好路径的数量 k 顶点。 仅当路径的顶点集不同时,路径才会被区分。

约束

  • 2 \le N \le 2 \times 10^5
  • 1 \le A_i < B_i \le N (1 \le i \le N - 1)
  • 给定的图是一棵树。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 B_1
A_2 B_2
\vdots
A_{N - 1} B_{N - 1}

输出

输出 N 行。

的 k- 第行应包含正确路径的数量 k 顶点。


示例输入 1

5
1 2
2 3
2 4
3 5

示例输出 1

0
1
3
2
0

最低分数为 1.

好的路径是以下六个路径。

  • 两个顶点连接顶点的路径 2 和 3
  • 三个顶点连接顶点的路径 1 和 3
  • 三个顶点连接顶点的路径 2 和 5
  • 三个顶点连接顶点的路径 3 和 4
  • 四个顶点连接顶点的路径 1 和 5
  • 四个顶点连接顶点的路径 4 和 5

示例输入 2

8
1 2
2 3
2 4
3 5
5 6
3 7
7 8

示例输出 2

1
3
7
8
5
0
0
0

示例输入 3

5
1 2
2 3
3 4
4 5

示例输出 3

0
0
0
0
1