Prüfer 序列

[giscus[bot]]

Prüfer 序列

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

https://oi-wiki.org/graph/prufer/

[NFLSCode]

为什么是线性的？指针不会不断往回跳然后扫过去吗？

[383494]

确实是线性的，以建树为例：ptr 不会往回，往回的只有 leaf。

[coder114514]

考虑这样一棵树：1,n-1,2,n-2,3,n-3,...floor(n/2),ceil(n/2),n 那那个线性构造的算法就是 O(n^2)的了...

[YOYO-UIAT]

这个页面为啥不在“树上问题”里啊

[xcr0987]

我也认为本文树转序列的“线性做法”可卡，于是去看了原文，发现：原文的确保证了线性，但本文的表述有不清晰之处，导致误解。
实际上，步骤 2 是不更改 $p$ 的，只需要循环删当前可删节点和查有没有新的可删节点即可，因为 $p$ 可以在上述操作后仍保持原有 $1$ 到 $p-1$ 间不存在叶节点的性质。

[Huasushis]

最开始我看线性做法也感觉有问题，后来仔细想了想发现很妙，觉得有比较重要的两点：

1. ptr是不会退的，只有leaf可能会退，不能更小的时候就继续从ptr往下搜。
2. 建树的时候一定要以 $n-1(从0开始)$ 为根，因为以其它点作为根都有可能成为叶子，然后被删掉导致发生错误。