2015多校第7场 HDU 5379 Mahjong tree 构造，DFS

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5379

题意：一颗n个节点n-1条边的树，现在要给每个节点标号（1~n），要求：（1）每一层的兄弟节点的标号要是连续的（2）每一颗子树的所有节点标号是连续的。问有多少种标号方案。

解法：对于每一层顶多只能存在2个非叶子节点，否则无解；对于每一层有x个叶子节点，y个非叶子节点，那么ans=(ans * x!)%mod，另外如果y!=0，还得ans=2*ans%mod。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = ;

const int mod = 1e9+;

int head[maxn],edgecnt, ks;

bool flag;

struct edge{

    int to,next;

}E[maxn*];

LL fac[maxn];

LL ans;

void init(){

    flag = ;

    ans = ;

    memset(head,-,sizeof(head));

    edgecnt=;

}

void INIT(){

    fac[] = ;

    for(int i=; i<maxn; i++){

        fac[i] = fac[i-]*i%mod;

    }

}

void add(int u,int v){

    E[edgecnt].to=v,E[edgecnt].next=head[u],head[u]=edgecnt++;

}

LL dfs(int u, int pre){

    if(!flag) return ;

    LL s = , all = , ss = ;

    //all代表叶子节点

    //ss代表非叶子节点

    for(int i = head[u]; ~i; i=E[i].next){

        int to = E[i].to;

        if(to == pre) continue;

        LL x = dfs(to, u);

        s += x;

        if(x == ) all++;

        else if(x>) ss++;

    }

    if(ss>) flag=false;

    else{

        ans=(ans*fac[all])%mod;

        if(ss!=) ans=(ans*2LL)%mod;

    }

    return s;

}

int main()

{

    ks = ;

    int T, n;

    INIT();

    scanf("%d", &T);

    while(T--){

        init();

        scanf("%d", &n);

        for(int i=; i<n; i++){

            int u,v;

            scanf("%d %d", &u,&v);

            add(u,v);

            add(v,u);

        }

        dfs(, -);

        if(n>) ans=ans*;

        if(!flag) ans=;

        printf("Case #%d: %lld\n", ++ks, ans%mod);

    }

    return ;

}