Hdu 5379 Mahjong tree (dfs + 组合数)

题目链接：

题目描述：

　　给出一个有n个节点的树，以节点1为根节点。问在满足兄弟节点连续以及子树包含节点连续的条件下，有多少种编号方案给树上的n个点编号？

解题思路：

　　对于一个节点来讲，非叶子儿子节点最多有两个才能满足要求，否则满足子树节点连续的话就无法满足兄弟节点连续。然后有dfs计算每棵子树的贡献值，每棵子树的子节点可以分为叶子节点X和非叶子节点Y，叶子节点可以分配到一组连续的编号，非叶子节点只能分配到兄弟节点中最大或者最小编号两种情况，叶子节点的贡献值为X!。然后dfs跑一下就ok咯。

 #include <queue>

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #pragma comment (linker, "/STACK:1024000000,1024000000")

 using namespace std;

 const int maxn = ;

 const int mod = (1e9 + );

 typedef long long LL;

 struct node

 {

     int to, next;

 }edge[maxn*];

 int head[][maxn], vis[maxn], tot, flag;

 LL res;

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[][from];

     head[][from] = tot ++;

     head[][from] ++;

 }

 void dfs (int u)

 {

     int k, cnt;

     k = cnt = ;

     vis[u] = ;

     for (int i=head[][u]; i!=-; i=edge[i].next)

     {

         int v = edge[i].to;

         if (vis[v])

             continue;

         if (!vis[v] && head[][v]==)

             cnt ++;

         else

             dfs (v);

         k ++;

     }

     if (k - cnt > )

     {

         res = ;

         return;

     }

     if (k != cnt)

         res = (res * ) % mod;

     while (cnt)

     {

         res = (res * cnt) % mod;

         cnt --;

     }

 }

 int main ()

 {

     int t, n, l = ;

     scanf ("%d", &t);

     while (t --)

     {

         scanf ("%d", &n);

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

         memset (head[], , sizeof(head[]));

         memset (vis, , sizeof(vis));

         tot = flag = ;

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

         {

             int u, v;

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

             Add (u, v);

             Add (v, u);

         }

         res = ;

         dfs ();

         printf ("Case #%d: %lld\n", ++l, n==?:res);

     }

     return ;

 }

巴特西

Hdu 5379 Mahjong tree (dfs + 组合数)

最新文章

热门文章