103034: [Atcoder]ABC303 E - A Gift From the Stars
Description
Score : $475$ points
Problem Statement
A graph with $(k+1)$ vertices and $k$ edges is called a level-$k\ (k\geq 2)$ star if and only if:
- it has a vertex that is connected to each of the other $k$ vertices with an edge, and there are no other edges.
At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:
- choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both $1$. Add an edge that connects the chosen two vertices.
He then arbitrarily assigned an integer from $1$ through $N$ to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it $T$. $T$ has $(N-1)$ edges, the $i$-th of which connects $u_i$ and $v_i$.
Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given $T$.
Constraints
- $3\leq N\leq 2\times 10^5$
- $1\leq u_i, v_i\leq N$
- The given graph is an $N$-vertex tree obtained by the procedure in the problem statement.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
Output
Suppose that Takahashi initially had $M$ stars, whose levels were $L=(L_1,L_2,\ldots,L_M)$. Sort $L$ in ascending order, and print them with spaces in between.
We can prove that the solution is unique in this problem.
Sample Input 1
6 1 2 2 3 3 4 4 5 5 6
Sample Output 1
2 2
Two level-$2$ stars yield $T$, as the following figure shows:
Sample Input 2
9 3 9 7 8 8 6 4 6 4 1 5 9 7 3 5 2
Sample Output 2
2 2 2
Sample Input 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
Sample Output 3
2 3 4 7
Input
题意翻译
一个具有 $(k+1)$ 个顶点和 $k$ 条边的图被称为一个级别为 $k（k\ge 2）$的菊花图，当且仅当： - 它有一个顶点与其他 $k$ 个顶点之间通过一条边相连，而其他顶点之间没有边。 起初，我们有一个由多个菊花图组成的图。重复以下操作，直到整个图变为一张连通图： - 选择图中的两个顶点。其中顶点之间必须是不连通的，并且它们的度数必须都是 $1$。将这两个顶点用一条边连接起来。 然后，在该过程后，他将整数从 $1$ 到 $N$ 随机分配给图中的每个顶点。生成的图是一棵树，我们称其为 $T$。$T$ 有 $(N-1)$ 条边，第 $i$ 条边连接了 $u_i$ 和 $v_i$。 给定 T，从小到大输出一开始的每个菊花图的 $k$。Output
分数：475分
问题描述
如果仅满足以下条件，则称一个具有$(k+1)$个顶点和$k$条边的图是一个级别为$k\ (k\geq 2)$的星形图：
- 它有一个顶点，通过一条边与其他$k$个顶点相连，且没有其他边。
起初，高桥有一个由星形图组成的图。 他重复以下操作，直到图中的每对顶点都相连：
- 在图中选择两个顶点。 在这里，顶点必须是断开的，且它们的度数都为$1$。 添加一条连接所选两个顶点的边。
然后，他任意地将从$1$到$N$的整数分配给操作后图中的每个顶点。 结果得到的图是一棵树；我们称之为$T$。 $T$有$(N-1)$条边，其中第$i$条边连接$u_i$和$v_i$。
现在，高桥已经忘记了他最初拥有的星形图的数量和级别。 根据$T$找出它们。
约束
- $3\leq N\leq 2\times 10^5$
- $1\leq u_i, v_i\leq N$
- 给定的图是一个通过问题描述中的过程得到的包含$N$个顶点的树。
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出：
$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
输出
假设高桥最初有$M$个星形图，它们的级别为$L=(L_1,L_2,\ldots,L_M)$。 将$L$按升序排序，并用空格分隔打印它们。
我们可以证明，在这个问题中解是唯一的。
样例输入1
6 1 2 2 3 3 4 4 5 5 6
样例输出1
2 2
两个级别为$2$的星形图可以得到$T$，如下图所示：
样例输入2
9 3 9 7 8 8 6 4 6 4 1 5 9 7 3 5 2
样例输出2
2 2 2
样例输入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