首页 > 代码库 > [BZOJ1211][HNOI2004]树的计数(Prufer序列)
[BZOJ1211][HNOI2004]树的计数(Prufer序列)
题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1211
分析:
关于无根树的组合数学问题肯定想到Prufer序列,类似bzoj1005那题
说下prufer序列的性质:
1、一个无根树对应一个prufer序列
2、一个n个节点无根树对应的prufer序列长度为n-2
3、prufer序列中某节点出现的次数==这个节点在对应的无根树中度数-1
所以这题求无根树的数量等价于求prufer序列的数量。
注意无解的情况就行了。
[BZOJ1211][HNOI2004]树的计数(Prufer序列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。