hdu 5379 Mahjong tree(構造)
題目:
Mahjong tree
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1471 Accepted Submission(s): 448
Problem Description Little sun is an artist. Today he is playing mahjong alone. He suddenly feels that the tree in the yard doesn't look good. So he wants to decorate the tree.(The tree has n vertexs, indexed from 1 to n.)
Thought for a long time, finally he decides to use the mahjong to decorate the tree.
His mahjong is strange because all of the mahjong tiles had a distinct index.(Little sun has only n mahjong tiles, and the mahjong tiles indexed from 1 to n.)
He put the mahjong tiles on the vertexs of the tree.
As is known to all, little sun is an artist. So he want to decorate the tree as beautiful as possible.
His decoration rules are as follows:
(1)Place exact one mahjong tile on each vertex.
(2)The mahjong tiles' index must be continues which are placed on the son vertexs of a vertex.
(3)The mahjong tiles' index must be continues which are placed on the vertexs of any subtrees.
Now he want to know that he can obtain how many different beautiful mahjong tree using these rules, because of the answer can be very large, you need output the answer modulo 1e9 + 7.
Input The first line of the input is a single integer T, indicates the number of test cases.
For each test case, the first line contains an integers n. (1 <= n <= 100000)
And the next n - 1 lines, each line contains two integers ui and vi, which describes an edge of the tree, and vertex 1 is the root of the tree.
Output For each test case, output one line. The output format is Case #x: ans(without quotes), x is the case number, starting from 1.
Sample Input
2
9
2 1
3 1
4 3
5 3
6 2
7 4
8 7
9 3
8
2 1
3 1
4 3
5 1
6 4
7 5
8 4
Sample Output
Case #1: 32
Case #2: 16
Author UESTC
Source 2015 Multi-University Training Contest 7
Recommend wange2014
題意:給一固定形態的樹,有n個節點,現在要給這n個節點賦值,每個節點取1到n的某個數,不能重復,並且滿足:1.任意節點的所有子節點的值必須連續 2.任意節點的子樹的值必須連續。 問有多少種賦值方法。
思路:由於這兩條規則的限制,不能有超過兩個非葉子節點,並且非葉子節點一定是取連續區間的端點。這樣的話非葉子節點有兩種取法,剩下的葉子節點有k!種取法,因為順序是任意的。所以對於某個根節點而言,它如果有孩子,那麼首先他有兩種取法,可以取區間最大或最小值,然後孩子中的葉子節點有k!取法,非葉節點再dfs下去求。
代碼:
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include