题目描述
Background
"Inheriting the Past"
Ysuperman responds to the call and decides to plant trees outside the kindergarten.
Nya nya, if so, Ysuperman can play games with the little friends in the hot summer.
Problem Description
To implement environmental protection efforts, Ysuperman has purchased a batch of trees, all of which look the same. Since the trees have not yet been planted, they do not have roots and can be considered as unrooted trees.
Ysuperman finds it boring to plant trees that all look the same, so TA invites a landscaping company to help with the planning. The landscaping company provides TA with a method—"grafting".
Below is the definition of the "grafting" operation:
A "leaf node" is defined as a node with a degree of $1$ in the tree.
The "grafting" operation refers to attaching a new "leaf node" to an unrooted tree.
For example:
Figure 2 is a tree obtained after a legal grafting operation on the tree in Figure 1, and Figure 3 is also a tree obtained after a legal grafting operation on the tree in Figure 1.
We also know that trees have a basic attribute: "species".
The "species" of a tree refers to the multiset formed by the maximum subtree size of each node.
Two trees have different "species" if and only if the multiset formed by the maximum subtree size of each node is different.
The maximum subtree size of a node here refers to the number of nodes in the largest connected component after removing this node.
For example:
The multiset of maximum subtree sizes for the tree in Figure 4 is: $\{2, 2, 3, 3\}$
The multiset of maximum subtree sizes for the tree in Figure 5 is: $\{2, 2, 3, 3\}$
The multiset of maximum subtree sizes for the tree in Figure 6 is: $\{1, 3, 3, 3\}$
Therefore, the tree in Figure 4 has the same "species" as the tree in Figure 5, but a different "species" from the tree in Figure 6.
Ysuperman wants to know how many different "species" of trees can be constructed through a single "grafting" operation, and for each "species", how many different "grafting" methods can be used to construct it. Please output the number of "grafting" methods for each "species" in ascending order.
Two "grafting" schemes are considered different if and only if the node directly connected to the newly attached "leaf node" in the "grafting" operation is different.
Input Format
The first line contains a number $n$.
The next $n-1$ lines, each containing two numbers $u, v$, indicate that there is an undirected edge between $u$ and $v$.
Output Format
The first line contains a number $cnt$, indicating how many different "species" of trees can be constructed.
The second line to the $cnt+1$-th line, output the number of "grafting" methods for each "species" in ascending order.
Sample Input and Output
Input Sample #1
5
1 2
2 3
3 4
4 5
Output Sample #1
3
1
2
2
Input Sample #2
7
1 2
1 3
2 4
2 5
3 6
3 7
Output Sample #2
3
1
2
4
Input Sample #3
25
15 9
22 15
23 22
25 15
13 23
6 22
12 15
1 23
19 13
18 9
11 15
17 1
4 25
3 1
8 9
20 1
10 18
21 20
16 8
2 22
24 1
7 19
5 16
14 7
Output Sample #3
17
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
3
Notes
This problem uses bundled testing.
Sample Explanation 1
One "species" of tree can be constructed with $\{2, 4, 4, 5, 5, 5\}$.
Two "species" of trees can be constructed with $\{3, 3, 4, 5, 5, 5\}$.
Two "species" of trees can be constructed with $\{3, 3, 4, 4, 5, 5\}$.
Sample Explanation 2
One "species" of tree can be constructed with $\{3, 5, 5, 7, 7, 7, 7, 7\}$.
Two "species" of trees can be constructed with $\{4, 4, 5, 7, 7, 7, 7, 7\}$.
Four "species" of trees can be constructed with $\{4, 4, 5, 6, 7, 7, 7, 7\}$.
For 100% of the data, it is guaranteed that $1 \le n \le 2 \cdot 10^6$.
A "chain" is defined as a tree where all nodes have a degree not exceeding $2$.
A "daisy" is defined as a tree containing $n-1$ "leaf nodes".
Special Property 1: The tree is guaranteed to be a "chain".
Special Property 2: The tree is guaranteed to be a "daisy".
Special Property 3: The tree is guaranteed to be a complete binary tree.
| Subtask | $n$ | Special Property | Score | Time Limit |
|---|---|---|---|---|
| 1 | $\le 2 \cdot 10^6$ | 2 | 2 | 4s |
| 2 | $\le 2 \cdot 10^6$ | 1 | 3 | 4s |
| 3 | $\le 300$ | None | 5 | 1s |
| 4 | $\le 2 \cdot 10^6$ | 3 | 7 | 4s |
| 5 | $\le 5000$ | None | 23 | 1s |
| 6 | $\le 5 \cdot 10^4$ | None | 29 | 2s |
| 7 | $\le 2 \cdot 10^6$ | None | 31 | 4s |
Hints:
If you do not know what a complete binary tree is, Ysuperman provides a link: Link.
The input and output are large, please use fast input and output methods.
If you use a recursive algorithm that requires a large stack space, you can first use sudo su to obtain permissions on a local (NOI Linux) machine, and then use the ulimit -s unlimited command to enable unlimited stack.
The problem is not difficult.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分