之前的版本
观前提示:可以用 alt+0252
打出来 ü 这个字符喵
1. 对树建立 Prüfer 序列
\(\rm Def.\) Prüfer 序列的构建如下:
每次选择树中编号最小的叶节点并删去它,并在一个初始为空的序列末加入其连接到的节点,直到整个树剩下 \(2\) 个节点(即 Prüfer序列 的长度为 \(n-1\))
实现
首先可以用堆,这显然是 \({\cal O}(n \log n)\) 的。
不过 Prüfer 序列也可以线性构造,过程:
0. 用一个指针 \(p\) 指向编号最小的叶节点;
- 删除 \(p\) 指向的节点;
- 如果产生新的叶节点,且编号小于原节点,删除之,并重复本步;
- 让 \(p\) 自增,直至指向一个未被删除的叶节点。
这个算法的正确性是有保证的,因为每次删除的一定是最小的叶节点。第 2 步中产生的新的叶结点中编号大于原节点的一定会在之后被扫描到。
时间复杂度上,\(p\) 至多自增 \(n-1\) 次,而第二步产生新的叶节点一定会消耗边,一棵树只有 \(n-1\) 条边,故总的时间复杂度是 \({\cal O}(n)\) 的。
2. 性质
- 最后剩下俩节点,其中必有 \(n\);
- 每个节点 \(v\) 出现 \({\rm deg}(v)-1\) 次。
3. 用 Prüfer 序列重构树
用 Prüfer 序列还原整棵树上节点的度数,找到序号最小的叶节点,prüfer 序列的第一个元素就是它的父节点。之后将它的父节点度数减一,继续之前的过程。
用堆维护,是 \({\cal O}(n \log n)\) 的。
重构也有线性的算法,和 [[Prüfer序列#实现|对树建立 Prüfer 序列的线性算法]] 如出一辙。
4. 代码
P6086 【模板】Prufer 序列
\({\cal O}(n \log n)\) 实现
void PtT() {for(int i = 1;i <= n-2;++i) deg[a[i]]++;for(int i = 1;i <= n;++i) if(deg[i] == 0) q.push(i);for(int i = 1;i <= n-2;++i) {b[q.top()] = a[i];q.pop();if(--deg[a[i]] == 0) q.push(a[i]);}for(int i = 1;i <= n-1;++i) {if(b[i] == 0) b[i] = n;ans ^= 1ll*i*b[i];}
}
void TtP() {for(int i = 1;i < n;++i) {deg[i]++;deg[a[i]]++;}for(int i = 1;i <= n;++i) if(deg[i] == 1) q.push(i);for(int i = 1;i <= n-2;++i) {b[i] = a[q.top()];q.pop();if(--deg[b[i]] == 1) q.push(b[i]);ans ^= 1ll*i*b[i];}
}
傻逼浓缩
int main() {
scanf("%d%d",&n,&m);
for(int i = 1;i <= n-m;++i)
scanf("%d",&a[0][i]);
if(m == 2)
a[0][n-1] = n;
for(int i = 1;i <= n-m;++i)
deg[a[0][i]]++;
for(int i = 1;i <= n;++i)
if(deg[i] == 0)
q.push(i);
m--;
for(int i[2] = {1,0};i[0] < n-(m^1);++i[0]) {
i[1] = q.top();
a[1][i[m]] = a[0][i[m^1]];
ans ^= 1ll*i[m]*a[1][i[m]];
q.pop()
if(--deg[a[1][i[m]]] == 0)
q.push(a[1][i[m]]);
}
printf("%lld\n",ans);
return 0;
}
\({\cal O}(n)\) 实现
void TtP() {for(int i = 1;i < n;++i) deg[a[i]]++;for(int p = 1, i = 0;p < n;++p) {int q = p;while(!deg[q]) {b[++i] = a[q];deg[a[q]]--;if(a[q] > p) break;q = a[q];}}
}
void PtT() {a[n-1] = n;for(int i = 1;i < n;++i) deg[a[i]]++;for(int p = 1, i = 0;p < n;++p) {int q = p;while(!deg[q]) {b[q] = a[++i];deg[b[q]]--;if(b[q] > p) break;q = b[q];}}
}
5. 凯莱公式
由上述 [[Prüfer序列#1. 对树建立 Prüfer 序列|Part 1]] 和 [[Prüfer序列#3. 用 Prüfer 序列重构树|Part 3]],我们得到了一个大小为 \(n\) 的无根树与长为 \(n-2\) 的序列之间的一一对应,所以我们可以证明 Cayley 公式:
\[\text{完全图}\ K_n\ \text{有}\ n^{n-2}\ \text{棵生成树。}
\]