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