首页 > 代码库 > [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序列)