社区讨论
如果你看不懂O(n)做法
P6086【模板】Prüfer(Prufer) 序列参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mllq1423
- 此快照首次捕获于
- 2026/02/14 10:52 5 天前
- 此快照最后确认于
- 2026/02/17 14:40 前天
感觉tj写的有的歧义这里补充一下
(自己理解的写法如果不正确请指出谢谢)
以m=1为例
应该是有两个指针，我们假设一个叫ptr，一个叫leaf，我们以从fa序列转为prufer序列为例
算法步骤如下：
- 将ptr、leaf置为最小的叶子的id
- 删去leaf，如果产生了新的叶子并且新叶子的id<ptr，则让leaf=新叶子的id，重复这一步
- 自增ptr，直到找到新叶子，让leaf=新叶子的id，回到第二步
因为ptr是递增的，++ptr对时间复杂度的贡献是O(n)，又因为每个点只会被删除一次，leaf乱跳对时间复杂度的贡献也是O(n)的
m=2同理
回复
共 1 条回复，欢迎继续交流。
正在加载回复...