#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 initially with nodes, all painted green. He has another rooted tree that he uses as a reference for his decorations. Mateo uses the following process to put on all of his decorations:
- For each node in , he creates a copy of the subtree rooted at . Let this copy be . Then, he paints the nodes of red. Finally, he chooses some green node in to be the parent of the root of by connecting them with an edge.
After applying all the decorations, ends up containing nodes. Unfortunately, he realized that he had forgotten to record what is! To make things worse, he accidentally spilled water on , washing off all the colour from the nodes. After all that, he labels the root of as 1, and then labels the rest of the nodes from 2 to .
The only information he currently has is the final state of , as well as . Help him find the number of possible that he could have started with, where two possibilities are considered different if they are structurally distinct.
Rooted trees and are said to be structurally identical if and only if they have the same number of nodes , and there is a way to label 's nodes from 1 to and 's nodes from 1 to such that:
- Their roots are labeled the same.
- Nodes labeled and in are connected by an edge if and only if nodes labeled and in are connected by an edge.
Otherwise, and are considered structurally distinct.
输入格式
The first line of input contains two space-separated integers and .
The next lines each contain two space-separated integers and (, ), describing an edge in connecting nodes and $v_
输出格式
Output the number of possible 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 is:
We can get 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 . The dotted lines represent the edges connecting the decorations to the tree.
Sample 2 Explanation
The first possibility for is:
Using this, we can get the following way:
The second possibility for is:
Using this, we can get the following way:
The following table shows how the available marks are distributed:
Marks Awarded | Bounds on | Bounds on |
---|---|---|
2 marks | ||
3 marks | ||
2 marks | ||
6 marks | ||
4 marks | ||
8 marks |