AT_abc303_e [ABC303E] A Gift From the Stars

题目描述

满足以下条件的 $k+1$ 个顶点和 $k$ 条边组成的图被称为等级为 $k$（$k \geq 2$）的星。

• 存在某一个顶点，与其他 $k$ 个顶点分别通过一条边相连。除此之外不存在其他边。

高桥君最初拥有一个由若干个星组成的图。然后，他重复执行以下操作，直到图中的所有顶点都连通为止。

• 从当前图的顶点中选择两个顶点。此时，所选的两个顶点的度数都为 $1$，且这两个顶点不连通。将这两个顶点之间连接一条边。

之后，高桥君对操作结束后的图的顶点随意编号为 $1$ 到 $N$。该图是一个树，记为 $T$。$T$ 有 $N-1$ 条边，第 $i$ 条边连接 $u_i$ 和 $v_i$。

后来，高桥君忘记了最初拥有的星的个数和等级。请根据 $T$ 的信息，求出最初拥有的星的个数和各自的等级。

输入格式

输入以以下格式从标准输入读入。

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出格式

假设高桥君最初拥有 $M$ 个星，各自的等级为 $L=(L_1,L_2,\ldots,L_M)$。请将 $L$ 按升序排列，并用空格分隔输出。

此外，可以证明本题的解是唯一确定的。

输入输出样例 #1

输入 #1

6
1 2
2 3
3 4
4 5
5 6

输出 #1

2 2

输入输出样例 #2

输入 #2

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

输出 #2

2 2 2

输入输出样例 #3

输入 #3

20
8 3
8 18
2 19
8 20
9 17
19 7
8 7
14 12
2 15
14 10
2 13
2 16
2 1
9 5
10 15
14 6
2 4
2 11
5 12

输出 #3

2 3 4 7

说明/提示

限制条件

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 给定的图是通过题目描述中的操作得到的 $N$ 个顶点的树
• 输入均为整数

样例解释 1

如下图所示，$T$ 可以由两个等级为 $2$ 的星得到。

由 ChatGPT 4.1 翻译