程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 5379 Mahjong tree(構造)

hdu 5379 Mahjong tree(構造)

編輯：關於C++

題目：

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

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
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define PB push_back
#define MP make_pair

#define REP(i,x,n) for(int i=x;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define FORD(i,h,l) for(int i=(h);i>=(l);--i)
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define RI(X) scanf(%d, &(X))
#define RII(X, Y) scanf(%d%d, &(X), &(Y))
#define RIII(X, Y, Z) scanf(%d%d%d, &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf(%d, &X)
#define DRII(X, Y) int X, Y; scanf(%d%d, &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf(%d%d%d, &X, &Y, &Z)
#define OI(X) printf(%d,X);
#define RS(X) scanf(%s, (X))
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
#define Swap(a, b) (a ^= b, b ^= a, a ^= b)
#define Dpoint  strcut node{int x,y}
#define cmpd int cmp(const int &a,const int &b){return a>b;}

 /*#ifdef HOME
    freopen(in.txt,r,stdin);
    #endif*/
const int MOD = 1e9+7;
typedef vector VI;
typedef vector VS;
typedef vector VD;
typedef long long LL;
typedef pair PII;
//#define HOME

int Scan()
{
	int res = 0, ch, flag = 0;

	if((ch = getchar()) == '-')				//判斷正負
		flag = 1;

	else if(ch >= '0' && ch <= '9')			//得到完整的數
		res = ch - '0';
	while((ch = getchar()) >= '0' && ch <= '9' )
		res = res * 10 + ch - '0';

	return flag ? -res : res;
}
/*----------------PLEASE-----DO-----NOT-----HACK-----ME--------------------*/


#define MAXN 100000
const int mod=1e9+7;
vectorg[MAXN+5];
int sz[MAXN+5];
int fact[MAXN+5];
int dfs(int u,int f)
{
    int ans=1;
    sz[u]=1;
    int son1=0;
    int son2=0;
    for(int i=0;i1)
            son2++;
        else
            son1++;
        sz[u]+=sz[v];

    }
    if(son2>2)
        return 0;
    if(son2!=0)
        ans=((long long)ans*2)%mod;
    ans=((long long )ans*fact[son1])%mod;

    return ans;
}
int main()
{int  T;
RI(T);
fact[0]=1;
for(int i=1;i<=MAXN;i++)
    fact[i]=((long long )fact[i-1]*i)%mod;
for(int t=1;t<=T;t++)
{
    int n;
    RI(n);
    for(int i=0;i<=n;i++)
        g[i].clear();
    for(int i=0;i1)
        ans=((long long )ans*2)%mod;
    printf(Case #%d: %d
,t,ans);


}



        return 0;
}