今天模拟赛被卡科技了，学一下这个东西，之前也看到很多次，只不过一直都没学。

算法简介

这是一种可以将带标号的树，转成唯一的整数序列表示的方法。而在“数树”题中也有大用。

算法流程大概是将带标号的 \(n\) 个节点的数用 \([1,n]\) 中的 \(n-2\) 个整数来表示一个树。

也可以理解成完全图的生成树和数列之间的双射。

算法流程

对树建立 \(prufer\) 序

具体什么是 \(prufer\) 序呢，就是每次将编号最小的叶节点取出来删掉，把他的父亲加入 \(prufer\) 序中，然后继续遍历下一个编号最小的叶节点。

所以我们显然用一个堆是能够很轻易的在 \(O(n\log n)\) 的时间复杂度中解决这个问题。

不过还有在线性时间中解决的算法。

1、考虑每次取出最小编号的叶节点，把他删掉。

2、令他父亲度数减一，判断他父亲度数是否为 \(0\) ，若为 \(0\) ，我们判断父亲节点是否编号小与当前节点，若小于，则一定父节点仍然是编号最小的父节点，那么我们就令父节点重复 \(1\) 操作。

这样为什么是对的呢，因为如果父节点小于当前节点编号，那么肯定是最小的，若不小于，那么在之后我们也可以枚举到。

因为每条边只会枚举一次，时间复杂度 \(O(n)\)

点击查看代码

for(int i=1;i<n;++i) {
	scanf("%lld",&fa[i]);
	++deg[fa[i]];
}
for(int i=1;i<=n;++i) {
	int x=i;
	while(deg[x]==0) {
		pru[++tot]=fa[x];
		--deg[fa[x]];
		if(fa[x]>i) break;
		x=fa[x];
	}
}

对 \(prufer\) 序建立树

也和上面很类似，每次我们先找到编号最小的点，那么当前枚举到的 \(prufer\) 序，一定是这个点的父亲，那么我们就令这个点的父亲度数减一，同样判断一下是否小于当前节点，然后依次类推就可以了。

不过要注意，因为编号最大的节点不会被删掉，所以我们要令第 \(n-1\) 个位置的 \(prufer\) 序为 \(n\)

点击查看代码

for(int i=1;i<=n-2;++i) {
	scanf("%lld",&pru[i]);
	++deg[pru[i]];
}
pru[n-1]=n;
int nw=0;
for(int i=1;i<=n;++i) {
	int x=i;
	while(deg[x]==0) {
		fa[x]=pru[++nw];
		--deg[fa[x]];
		if(fa[x]>i) break;
		x=fa[x];
	}
}