Prufer序列

Prufer序列

构造与转换

  树->序列 步骤:(是树,而不是森林)

    ①、找到当前度数最小的点x(相同的取标号小的)

    ②、删除x及其边。将所有与x相邻的点加入当前prufer序列后面。

  不断重复①、②直到图中只有两个点。

  序列->树 步骤:(保证树原本序号为排列,设G={1..n})

    ①、找到G在Prufer序列中未出现的最小数x

    ②、x向Prufer序列首项y连边,然后将x从G中删除,将Prufer首项删除(只删一个)。

  不断重复①、②直到G中只有两个点,连一条边。

性质

  设树中每个点度数为$d_i$,那么点i会在Prufer序列中出现$d_i-1$次。ps:$\sum d_i=2*n-2$

  不同的Prufer序列对应不同的无根树。(没有出现的都按钦点的顺序连边,以保证标号不同)

  不同的定义:树形不同或标号不同。(不能经过旋转拉伸变成一样的树)

例题

  BZOJ1211:给出每个点的度数,求不同合法的树个数。

  根据上述构造方法:$Ans=(n-2)!*\prod  \frac{1}{(d_i-1)!}$ 或者利用排列数计算

  程序实现(排列计算):

for(Ans=1,sum=0,i=1;i<=n;i++)
     Ans*=A(n-2-sum,di-1),sum+=di-1;//A(x,y)=x!/(x-y)!

  ps:该题需要判树不存在的情况。

  BZOJ1005:有些点度数未知,求不同合法的树个数。

  记Sum为已知度数的方案数,Sd为已知点的$\sum d_i -1$,m为未知的点数,$Ans=Sum*C(n-2,n-2-Sd)*m^{n-2-Sd}$

?  大概需要一个高精度。T^T

  BZOJ1430:自己看题吧。

  $Ans=(n-1)!*n^{n-2}$ ps:$n^{n-2}$意味无根树个数,$(n-1)!$即边的出现顺序。

  注意long long...

总结

  利用性质转换为序列问题,然后组合数求解。

时间: 05-28

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序列的数量. 注意无解的情况就行了.

POJ 2567 Code the Tree &amp;amp; POJ 2568 Decode the Tree Prufer序列

题目大意:2567是给出一棵树,让你求出它的Prufer序列.2568时给出一个Prufer序列,求出这个树. 思路:首先要知道Prufer序列.对于随意一个无根树,每次去掉一个编号最小的叶子节点,并保存这个节点所连接的节点所得到的序列就是这棵树的Prufer序列. 这个序列有十分优雅的性质.它能与无根树一一相应.因此.两个标号一样的无根树得到的Prufer序列也一定是一样的. 此外,设一个节点的度数是d[i],那么他会在Prufer序列中出现d[i] - 1次. 2567:记录每个节点的度.依

BZOJ 1005 明明的烦恼(prufer序列+高精度)

有一种东西叫树的prufer序列,一个树的与一个prufer序列是一一对应的关系. 设有m个度数确定的点,这些点的度为dee[i],那么每个点在prufer序列中出现了dee[i]-1次. 由排列组合可以推出公式.需要用高精度. #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define M 1100 using namespace std; typede

POJ 2567 Code the Tree &amp; POJ 2568 Decode the Tree Prufer序列

题目大意:2567是给出一棵树,让你求出它的Prufer序列.2568时给出一个Prufer序列,求出这个树. 思路:首先要知道Prufer序列.对于任意一个无根树,每次去掉一个编号最小的叶子节点,并保存这个节点所连接的节点所得到的序列就是这棵树的Prufer序列.这个序列有十分优雅的性质,它能与无根树一一对应.因此,两个标号一样的无根树得到的Prufer序列也一定是一样的.此外,设一个节点的度数是d[i],那么他会在Prufer序列中出现d[i] - 1次. 2567:记录每一个节点的度,按照

BZOJ 1005 明明的烦恼 Prufer序列+组合数学+高精度

题目大意:给定一棵n个节点的树的节点的度数,其中一些度数无限制,求可以生成多少种树 Prufer序列 把一棵树进行以下操作: 1.找到编号最小的叶节点,删除这个节点,然后与这个叶节点相连的点计入序列 2.反复进行1,直到这棵树只剩下两个节点时,退出 比如说这个图(来自度受百科) 最小叶节点为2,删除2,将3计入序列 最小叶节点为4,删除4,将5计入序列 最小叶节点为5,删除5,将1计入序列 最小叶节点为1,删除1,将3计入序列 图中只剩下两个节点,退出 于是得到这棵树的Prufer序列为{3,5

【BZOJ 1211】 1211: [HNOI2004]树的计数 (prufer序列、计数)

1211: [HNOI2004]树的计数 Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2468  Solved: 868 Description 一个有n个结点的树,设它的结点分别为v1, v2, -, vn,已知第i个结点vi的度数为di,问满足这样的条件的不同的树有多少棵.给定n,d1, d2, -, dn,编程需要输出满足d(vi)=di的树的个数. Input 第一行是一个正整数n,表示树有n个结点.第二行有n个数,第i个数表示di,即

BZOJ 1211 HNOI2004 树的计数 Prufer序列

题目大意:给定一棵树中所有点的度数,求有多少种可能的树 Prufer序列,具体参考[HNOI2008]明明的烦恼 直接乘会爆long long,所以先把每个数分解质因数,把质因数的次数相加相减,然后再乘起来 注意此题无解需要输出0 当n!=1&&d[i]==0时 输出0 当Σ(d[i]-1)!=n-2时输出0 写代码各种脑残--居然直接算了n-2没用阶乘-- #include<cstdio> #include<cstring> #include<iostrea

【BZOJ1005/1211】[HNOI2008]明明的烦恼/[HNOI2004]树的计数 Prufer序列+高精度

[BZOJ1005][HNOI2008]明明的烦恼 Description 自从明明学了树的结构,就对奇怪的树产生了兴趣......给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? Input 第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1 Output 一个整数,表示不同的满足要求的树的个数,无解输出0 Sample Input 3 1 -1 -1 Sample Outp

【bzoj1005】[HNOI2008]明明的烦恼 Prufer序列+高精度

题目描述 给出标号为1到N的点,以及某些点最终的度数,允许在任意两点间连线,可产生多少棵度数满足要求的树? 输入 第一行为N(0 < N < = 1000),接下来N行,第i+1行给出第i个节点的度数Di,如果对度数不要求,则输入-1 输出 一个整数,表示不同的满足要求的树的个数,无解输出0 样例输入 3 1 -1 -1 样例输出 2 题解 Prufer序列+高精度 Prufer序列:由一棵 $n$ 个点的树唯一产生的一个 $n-2$ 个数的序列. 生成方法:找到这棵树编号最小的叶子节点,将其