前言
- msjing一下午学了 \(4\) 个东西，现在非常有精神
这个紫题和我上午刷的真的是同一个难度吗
——msjing
Prüfer简介及操作
- 这个玩意看起来好吊的样子，那这究竟是个啥呢
Prüfer可以将一个带标号 \(n\) 个结点的树用 \([1,n]\) 中的 \(n-2\) 个整数表示．你也可以把它理解为完全图的生成树与数列之间的双射，常用组合计数问题中。
——oiwiki
计算序列
- 这样的话一个有标无根树就可以表示了，具体怎么操作呢
- 每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点．重复 \(n-2\) 次后就只剩下两个结点，算法结束。
- 我们来徒手模拟一下
- ~~c这个CS Academy怎么加载这么慢，算了画吧，欸你怎么加载好了~
艹浏览器突然无了图啥的全没了请忽视字体和图大小不一和 HZ 保密画质- 我们有了这个序列之后，我们就可以还原这块树了，怎么还原呢
树的还原
- 性质：
- 每个结点在序列中出现的次数是其度数 \(-1\)。
- 没有出现的是叶子结点
- 有了这个，我们就可以依据数列还原了
- 我们选一个度数为 \(1\) 的编号最小的点，与当前枚举到的序列的点连接，然后同时减掉两个点的度，不断重复，直到最后剩下两个度数为 \(1\) 的点，把它们连上就行了，度用桶维护，给图（图中是先把 \(5\) 和 \(7\) 连上了）
- 我们可以结合图与表清晰理解
线性构造序列和还原树
- 不想写，咕咕咕
后话
- msjing学的非常草率，所以就现这样吧（·W·）