[hdu5379 Mahjong tree]dfs计数-白红宇

[hdu5379 Mahjong tree]dfs计数

阅读量：5348 次

发布时间：2019-06-15

本文共 2917 字，大约阅读时间需要 9 分钟。

题意：给n个节点的树编号1-n，一个节点唯一对应一种编号，要求编完号的树满足如下性质：所有节点的儿子的编号是连续的，对一棵子树，它包含的所有节点的编号也是连续的。连续的意思是把所有数排序后是一段连续的区间。

思路：由于所有子树是连续的，所以可以用区间来表示子树，设要给当前子树编号为[1,n]，如果当前子树是原树，那么根有两种选择，分别是放头和尾（如果n等于1，那么头和尾重合了，也就是只有1种选择），如果不是原树，那么根的选择是唯一的，因为在考虑它的父亲的时候，它的位置就确定了。如果它的非叶子节点的儿子数目超过两个，显然是无解的，否则就有解，设叶子节点的儿子个数为cnt，答案就是cnt!，如果有非叶子节点的儿子，那么这个儿子可以放头也可以放尾，答案还要乘上2。

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99100101102103104105106107108109110111112113114115116

#pragma comment(linker, "/STACK:1024000000")#include #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       using namespace std;#define X first#define Y second#define pb push_back#define mp make_pair#define all(a) (a).begin(), (a).end()#define fillchar(a, x) memset(a, x, sizeof(a))#define copy(a, b) memcpy(a, b, sizeof(a))typedef long long ll;typedef pair
                       
                         pii;typedef unsigned long long ull;//#ifndef ONLINE_JUDGEvoid RI(vector
                        
                         &a,int n){a.resize(n);for(int i=0;i
                         
                          void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){ int d=p
                          
                           void print(const T t){cout<
                           
                            <
                            
                             
                              void print(const F f,const R...r){cout<
                              
                               <<", ";print(r...);}template
                               
                                void print(T*p, T*q){ int d=p
                                
                                 <<*p<<", ";p+=d;}cout<
                                 
                                  bool umax(T&a, const T&b){ return b<=a?false:(a=b,true);}template
                                  
                                   bool umin(T&a, const T&b){ return b>=a?false:(a=b,true);}template
                                   
                                    void V2A(T a[],const vector
                                    
                                     &b){ for(int i=0;i
                                     
                                      
                                       void A2V(vector
                                       
                                        &a,const T b[]){ for(int i=0;i
                                                                                  > G; void clear() { G.clear(); } void resize(int n) { G.resize(n + 2); } void add(int u, int v) { G[u].push_back(v); } vector
                                         
                                           & operator [] (int u) { return G[u]; }};Graph G;bool vis[maxn];int SZ[maxn], fac[maxn];void pre_init() { fac[0] = 1; for (int i = 1; i < maxn; i ++) fac[i] = (ll)fac[i - 1] * i % md;}int dfs(int rt) { vis[rt] = true; SZ[rt] = 1; int cnt1 = 0, cnt2 = 0, ans = 1; for (int i = 0; i < G[rt].size(); i ++) { int v = G[rt][i]; if (!vis[v]) { ans = (ll)ans * dfs(v) % md; SZ[rt] += SZ[v]; if (SZ[v] <= 1) cnt1 ++; else cnt2 ++; } } if (cnt2 > 2) return 0; ans = (ll)ans * fac[cnt1] % md; return cnt2? 2 * ans % md : ans;}int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif // ONLINE_JUDGE int T, cas = 0, n, u, v; pre_init(); cin >> T; while (T --) { cin >> n; G.clear(); G.resize(n); for (int i = 1; i < n; i ++) { scanf("%d%d", &u, &v); G.add(u, v); G.add(v, u); } fillchar(vis, 0); fillchar(SZ, 0); printf("Case #%d: %d\n", ++ cas, dfs(1) * (n >= 2? 2 : 1) % md); } return 0;}

转载于:https://www.cnblogs.com/jklongint/p/4724236.html

你可能感兴趣的文章