hdu5379Mahjong tree

题意：给出一棵树，用[1,n]里的n个不同的数去给结点标号，要求任意结点的儿子标号都是连续的，任意子树里的标号也都是连续的。求这样标号的方法有多少种。

做法：很显然，若一个结点有大于两个的儿子必然无解。

若当前有x个连续的数可以用来分配，那么这个结点要么取最小的那个数，要么取最大的那个数，

当该结点刚好有两个不为叶子的儿子，然后剩下的那x-1个数要么把前面的部分给左边的儿子要么给右边的儿子，后面的部分一样，这就有2种可能。

当刚好有一个不为叶子的儿子，那么剩下的那x-1个数要么把前面的部分给儿子，要么把后面的部分给儿子，这就有2种可能。

若没有上述的儿子，则全是叶子，则就是(x-1)!可能，上述两种情况考虑儿子为叶子的时候同理。

接下来就是很裸的树形dp了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
struct Edge
{
    int to,next;
}edge[200010];
int head[100010],tail;
void add(int from,int to)
{
    edge[tail].to=to;
    edge[tail].next=head[from];
    head[from]=tail++;
}
bool vis[100010];
int num[100010];
void seek(int from)
{
    vis[from]=1;
    num[from]=1;
    for(int i=head[from];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to])
            continue;
        seek(to);
        num[from]+=num[to];
    }
}
ll fac[100010];
ll dfs(int from)
{
    vis[from]=1;
    int sum1=0,sum2=0;
    vector<int>bx;
    for(int i=head[from];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(vis[to])
            continue;
        if(num[to]==1)
            sum1++;
        else
        {
            sum2++;
            bx.push_back(to);
        }
    }
    if(sum2>2)
    {
        return 0;
    }
    if(sum2==0)
        return fac[sum1];
    ll sum=1;
    for(int i=0;i<sum2;i++)
    {
        ll t=dfs(bx[i]);
        if(t==0)
            return 0;
        sum=(sum*t)%mod;
    }
    return fac[sum1]*sum*2%mod;
}
int main()
{
    fac[0]=1;
    for(int i=1;i<=100000;i++)
        fac[i]=fac[i-1]*i%mod;
    int T;
    scanf("%d",&T);
    for(int cs=1;cs<=T;cs++)
    {
        int n;
        scanf("%d",&n);
        tail=0;
        memset(head,-1,sizeof(head));
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            add(u,v);
            add(v,u);
        }
        if(n==1)
        {
            printf("Case #%d: 1\n",cs);
            continue;
        }
        memset(vis,0,sizeof(vis));
        seek(1);
        memset(vis,0,sizeof(vis));
        printf("Case #%d: %d\n",cs,int(2*dfs(1)%mod));
    }
    return 0;
}

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

Case #1: 32
Case #2: 16

hdu5379Mahjong tree

原文：http://blog.csdn.net/stl112514/article/details/47447451