首页 > 其他分享 >Prufer序列

Prufer序列

时间:2023-07-28 11:44:43浏览次数:42  
标签:Pr 叶子 fer 编号 序列 Prufer 节点

P6086 【模板】Prüfer 序列

Prüfer 序列可以将树的计数问题转化为序列,而且可以和树实现 \(O(n)\) 互相转换。

Prüfer 序列定义:对于一颗无根树,每次选择一个编号最小的叶子节点(定义为度为 \(1\) 的点),记录它的父节点,直到最后只剩下两个点(因为节点 \(n\) 一定不会被删,是个常量,没有必要记录)。

二者是唯一对应的。

转换方法

Prüfer 转树

显然可以带 \(\log\) 转换,但是有 \(O(n)\) 的方法。

考虑维护一个变量 \(j\) 表示现在已知的最小的编号的叶子节点,逐步增加,遇到第一个叶子节点时:

  1. 加入序列。
  2. 查看其父亲的编号是否小于它且成为叶子节点,如果小于加入其父亲,不断往上迭代。

由于每次循环 Prüfer 序列长度都会增加 \(1\),所以复杂度显然。

树转 Prüfer

类似做法。

除 \(n\) 外,每个节点的度为它在 Prüfer序列中出现的次数。

同上,遇到情况时的区别:

  1. 更新父亲。
  2. 同上2.。

code

标签:Pr,叶子,fer,编号,序列,Prufer,节点
From: https://www.cnblogs.com/wscqwq/p/17587185.html

相关文章

  • 代码随想录算法训练营第四十天| 300.最长递增子序列 674. 最长连续递增序列 718.
    300.最长递增子序列要求:可以删减任意个节点,最后保存最大的递增长度难点:410489如何保证全局的视角,看到很前面的节点是否大于当前的节点,而不是仅仅记录状态思路:dp[n],当子序列的末尾为N时,它的最大子序列长度也就意味着,N在它的子序列中是最大的,遍历这个N之前的所有序......
  • 比JDK最高快170倍,蚂蚁开源一款序列化框架!
    点击“终码一生”,关注,置顶公众号每日技术干货,第一时间送达! Fury是一个基于JIT动态编译和零拷贝的多语言序列化框架,支持Java/Python/Golang/JavaScript/C++等语言,提供全自动的对象多语言/跨语言序列化能力,和相比JDK最高170倍的性能。GitHub地址为:https://github.com/al......
  • P2127 序列排序 题解
    原题题目意思\(有一个数列a,每次可以挑选任意两个元素交换位置,代价为这两个元素的和,问把序列a升序排序所需的最小总代价\)\(定义数列上的一个有i个元素的环S使得s_1要换到s_2,s_2要到s_3,……,s_i要到s_1\)\(原图一个元素只有一个目标位置,所以可以看作一个有n点,n边的有向图\)......
  • PHP 中优雅的将JSON/XML/YAML 等数据反序列化成指定的类对象
    这个小事情何以需要记上一笔?实在是因为当用了各种编程语言以后,发现系统I/O处,尤其对外的接口Interface最重要,它或许可以被称为Specification,规约。PHP是混合型编程风格的语言,不强求完全的OOP。但是代码不OOP化的话,又得不到更多的开发工具的支持。尤其在PHP中如果只是用数组结......
  • 关于视图类和序列化类的知识
    1.代码classPayOrderView(GenericViewSet):serializer_class=PaySerializerdefcreate(self,request,*args,**kwargs):ser=self.get_serializer(context={'request':request},data=request.data)ser.is_vaild(raise_exceptio......
  • JAVA 序列化(创建可复用的 Java 对象)
    保存(持久化)对象及其状态到内存或者磁盘Java平台允许我们在内存中创建可复用的Java对象,但一般情况下,只有当JVM处于运行时,这些对象才可能存在,即,这些对象的生命周期不会比JVM的生命周期更长。但在现实应用中,就可能要求在JVM停止运行之后能够保存(持久化)指定的对象,并在将......
  • 帆软channel反序列化漏洞
    一级测试一级级测试测试二级测试测试三级测试二级测试......
  • 数据分享|SAS与eviews用ARIMA模型对我国大豆产量时间序列预测、稳定性、白噪声检验可
    全文链接:http://tecdat.cn/?p=31480最近我们被客户要求撰写关于ARIMA的研究报告,包括一些图形和统计输出。我国以前一直以来都是世界上大豆生产的第一大国。但由于各国的日益强大,导致我国豆种植面积和产量持续缩减。因此,预测我国的大豆产量对中国未来的经济发展有着极其重要的作......
  • Postgres学习笔记-Sequence自增序列
    Sequence:根据指定的规范生成整数序列创建序列CREATE[TEMPORARY|TEMP]SEQUENCEname[INCREMENT[BY]increment][MINVALUEminvalue|NOMINVALUE][MAXVALUEmaxvalue|NOMAXVALUE][START[WITH]start][CACHEcache][[NO]CYCLE]......
  • python jsonpickle模块不序列化私有变量
    jsonpickle模块可以把对象序列化为JSON文件,还是比较方便的.但是并不是所有变量都需要序列化的,比如有些私有变量就不需要序列化,下面是实现方法:importjsonpickleclassNoSerailPrivates:'''表示不序列化私有变量,以_开头都变量'''def__getstate__(self):......