#P12967. [CCO 2025] Tree Decorations

[CCO 2025] Tree Decorations

题目描述

Mateo recently found the perfect decorations for his Christmas tree — more trees!

Specifically, his Christmas tree is a rooted tree TT initially with MM nodes, all painted green. He has another rooted tree DD that he uses as a reference for his decorations. Mateo uses the following process to put on all of his decorations:

  • For each node ii in DD, he creates a copy of the subtree rooted at ii. Let this copy be CiC_i. Then, he paints the nodes of CiC_i red. Finally, he chooses some green node in TT to be the parent of the root of CiC_i by connecting them with an edge.

After applying all the decorations, TT ends up containing NN nodes. Unfortunately, he realized that he had forgotten to record what DD is! To make things worse, he accidentally spilled water on TT, washing off all the colour from the nodes. After all that, he labels the root of TT as 1, and then labels the rest of the nodes from 2 to NN.

The only information he currently has is the final state of TT, as well as MM. Help him find the number of possible DD that he could have started with, where two possibilities are considered different if they are structurally distinct.

Rooted trees AA and BB are said to be structurally identical if and only if they have the same number of nodes SS, and there is a way to label AA's nodes from 1 to SS and BB's nodes from 1 to SS such that:

  • Their roots are labeled the same.
  • Nodes labeled xx and yy in AA are connected by an edge if and only if nodes labeled xx and yy in BB are connected by an edge.

Otherwise, AA and BB are considered structurally distinct.

输入格式

The first line of input contains two space-separated integers NN and MM.

The next N1N - 1 lines each contain two space-separated integers uiu_i and viv_i (1ui,viN1 \leq u_i, v_i \leq N, uiviu_i \neq v_i), describing an edge in TT connecting nodes uiu_i and $v_

输出格式

Output the number of possible DD that he could have started with, where two possibilities are considered different if they are structurally distinct.

8 3
1 2
1 3
1 4
2 5
2 6
3 7
3 8
1
14 5
1 2
1 3
3 4
3 5
1 6
6 7
7 8
7 9
2 10
10 11
10 12
10 13
10 14
2

提示

Sample 1 Explanation

It is provable that the only possible DD is:

We can get TT the following way:

In the diagram above, the red parts are added as decorations, while the green, filled-in part represents the initial state of TT. The dotted lines represent the edges connecting the decorations to the tree.

Sample 2 Explanation

The first possibility for DD is:

Using this, we can get TT the following way:

The second possibility for DD is:

Using this, we can get TT the following way:

The following table shows how the available 2525 marks are distributed:

Marks Awarded Bounds on NN Bounds on MM
2 marks 2N102 \leq N \leq 10 M=1M = 1
3 marks 2N2002 \leq N \leq 200
2 marks 2N5000002 \leq N \leq 500000
6 marks 2N2002 \leq N \leq 200 1M<N1 \leq M < N
4 marks 2N20002 \leq N \leq 2000
8 marks 2N5000002 \leq N \leq 500000