首页 > 其他分享 >prufer序列-学习笔记

prufer序列-学习笔记

时间:2022-12-11 19:55:50浏览次数:62  
标签:度数 结点 int 特判 笔记 序列 prufer

引入

一个小知识,稍微学一下

其实 prufer 序列就是一种将带标号的树用一个唯一的整数序列表示的方法.

(小知识 prüfer 是德语,所以应该读作/代码里应该写作 pruefer)

定义

每次选择一个编号最小的叶结点并删掉它,然后在序列中记录下它连接到的那个结点。重复 \(n-2\) 次后就只剩下两个结点

終わった!很简单的啦(

小性质

  1. 是一个双射(一一对应)
  2. 在构造完 prufer 序列后原树中会剩下两个结点,其中一个一定是编号最大的点
  3. 每个结点在序列中出现的次数是其度数减 \(1\)(没有出现的就是叶结点)

代码

代码也很好实现(看代码就看得懂吧,反正博客是给自己看的(bushi)(代码的题目链接

这个是 \(O(n\log n)\) 的做法,有 \(O(n)\) 的做法,可惜我不会.

int n,m;
int fa[N],pf[N],deg[N];
void t_to_p() //父亲序列转 prufer 序列
{
	int cnt=0;
	for(int i=1; i<n; i++) deg[fa[i]]++; //记录节点的度
	priority_queue<int, vector<int>, greater<int> > q; //用堆维护
	for(int i=1; i<=n; i++) if(deg[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.top(); q.pop();
		pf[++cnt]=fa[u]; deg[fa[u]]--; if(deg[fa[u]]==0) q.push(fa[u]);
	} //每次把编号最小的叶子结点取出来,更新prufer序列,然后如果原来的父亲成为叶子,再加进去
}

void p_to_t() // prufer 序列转父亲序列
{
	for(int i=1; i<=n; i++) deg[i]=1;
	for(int i=1; i<=n-2; i++) deg[pf[i]]++; //根据性质,可以求出节点的度
	priority_queue<int, vector<int>, greater<int> > q; //用堆维护
	for(int i=1; i<=n; i++) if(deg[i]==1) q.push(i);
	int t=1; pf[n-1]=n;
	while(!q.empty())
	{
		int u=q.top(); q.pop();
		fa[u]=pf[t],t++;
		deg[u]--,deg[fa[u]]--;
		if(deg[fa[u]]==1) q.push(fa[u]);
	} //每次取出编号最小的度数为1的点,然后连向它的父亲(
}

小应用

例子1

完全图生成树个数(无标号)(Cayley 公式)

\(n\) 个点,prufer 序列有 \(n^{n-2}\) 种,所以生成树个数也是这个.

完全图生成树个数(有标号)

\(n^{n-2}\cdot n!\) (不然呢?不就是加个顺序

例子2

[HNOI2004]树的计数

一个有 \(n\) 个节点的树,设它的节点分别为 \(v_1,v_2,\cdots,v_n\) ,已知第 \(i\) 个节点 \(v_i\) 的度数为 \(d_i\),问满足这样的条件的不同的树有多少棵.

题解:prufer序列中,每个节点出现的次数是 \(d_i-1\),所以其实就是一个可重集排列,答案为 \(\displaystyle\frac{(n-2)!}{\prod_{i=1}^n (d_i-1)!}\)

有一些特判,\(n=1\) 的时候要特判,有度数为零的要特判,度数加起来不等于 \(2n-2\) 要特判

标签:度数,结点,int,特判,笔记,序列,prufer
From: https://www.cnblogs.com/copper-carbonate/p/16974272.html

相关文章

  • Rocky9 编译安装 Nginx Mariadb Asp.net Core6 (实测 笔记)
    一、查看硬件信息查看物理cpu个数、核心数量、线程数grep'physicalid'/proc/cpuinfo|sort-u|wc-lgrep'coreid'/proc/cpuinfo|sort-u|wc-lgrep'process......
  • 离散数学--关键leeds笔记
    TypesofProofdirectproofProveα→βby:assumeαistrueusethistoderiveβ.indirectproofaproofthatisnotdirect;includes:proofbycontraposition......
  • JDK 新特性学习笔记之模块系统
    封装是指将数据与操作该数据的方法捆绑在一起。而信息隐藏是隐藏实现细节。封装和信息隐藏常常出现在一起,以致于它们几乎成了同义词,在一些上下文,它们也的确是同义词。封装提......
  • jupyterlab学习笔记
    1相关包安装1.1miniconda安装#下载安装包https://docs.conda.io/en/latest/miniconda.html1.2nodejs安装#下载地址https://nodejs.org/en/1.3git安装#下......
  • 【《硬件架构的艺术》读书笔记】04 时钟分频器
    4.1介绍偶数时钟分频很好实现,使用一个计数器累加到一定值再清零,同时翻转电平就可以了。本章主要讲的是奇数分频和小数分频。4.2同步整数分频器使用Moore状态机可以轻......
  • JavaScript笔记 - 防抖与节流
    防抖与节流目录防抖与节流1.防抖2.节流在进行窗口操作或者输入框操作时,如果事件处理函数触发频率过高,会加重浏览器和服务器的负担。此时可以使用防抖和节流的方式来减......
  • 拓端tecdat|R语言模拟ARCH过程模型分析时间序列平稳性、波动性
    在事物的发展过程中,常表现出复杂的波动情况,即时而波动的幅度较缓,而又时常出现波动集聚性(VolatilitYclustering),在风险研究中经常遇到这种情况。恩格尔(Engle)在1982年提......
  • ES6笔记 - Promise对象
    Promise对象目录Promise对象1.Promise简介2.Promise的使用2.1创建Promise对象2.2Promise的执行时间2.3简写形式3.then方法4.catch方法5.all方法和race方法6.reso......
  • #yyds干货盘点# react笔记之学习之事件
    前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从......
  • #yyds干货盘点# react笔记之学习之使用组件完成练习
     我是歌谣放弃很容易但是坚持一定很酷日期部分data.jsimportReactfrom'react';import'./MyDate.css';constMyDate=()=>{return(<divclassName="d......