prufer

· · 个人记录

题意：HNOI2004 树的技术

一个n个节点的数，每个节点有一个度数，求有多少种不同的树每个节点的度数满足条件。

这是一个prufer序列的裸题：

prufer序列

prufer序列是一种对有标号无根树的编码，长度为节点数-2

具体的，存在无根树转为prufer序列以及prufer序列转化为无根树，换言之两者可以相互转化。

一.无根树转prufer

1.找到编号最小且度数为1的点。 2.删除该节点，并在序列中添加与该节点连接的节点。 3.重复1，2操作，直到树上只有两个节点（此时在进行操作没有意义，所以停止，这也就是为什么prufer序列长度为节点数-2）

二.prufer转为无根树 1.设prufer序列的集合为M，另一个集合G{1,2,3...n} 2.每次提取M中最靠前的元素与G中不存在与M且最靠前的元素v,将u与v连边，分别在两个集合中删除u，v。 3.最后将G中剩下的连个元素连边。

对于这道题

ans=(n-2)!/((d_{1}-1)!*(d2-1)!*...*(d_{n}-1)!)

特判几个地方，当转换prufer的时候，如果入列次数!=n-2,输出0，节点数为0的时候也输出0.