博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[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

你可能感兴趣的文章
mysql操作命令梳理(4)-中文乱码问题
查看>>
Python环境搭建(安装、验证与卸载)
查看>>
一个.NET通用JSON解析/构建类的实现(c#)
查看>>
关于这次软件以及pda终端的培训
查看>>
如何辨别一个程序员的水平高低?是靠发量吗?
查看>>
新手村之循环!循环!循环!
查看>>
线程安全问题
查看>>
linux的子进程调用exec( )系列函数
查看>>
MySQLdb & pymsql
查看>>
zju 2744 回文字符 hdu 1544
查看>>
【luogu P2298 Mzc和男家丁的游戏】 题解
查看>>
前端笔记-bom
查看>>
上海淮海中路上苹果旗舰店门口欲砸一台IMAC电脑维权
查看>>
Google透露Android Market恶意程序扫描服务
查看>>
给mysql数据库字段值拼接前缀或后缀。 concat()函数
查看>>
迷宫问题
查看>>
【FZSZ2017暑假提高组Day9】猜数游戏(number)
查看>>
泛型子类_属性类型_重写方法类型
查看>>
对闭包的理解
查看>>
练习10-1 使用递归函数计算1到n之和(10 分
查看>>