Prüfer / Prufer 序列

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132090250

​

快速跳转

结论：一个完全图的生成树个数为 nn−2n^{n-2}

注意，生成树是指无根树

构造过程

从小到大枚举叶子节点（指度数为1的点），记录其父亲。
在这里插入图片描述

最终为｛2，2，3，3，2｝

考虑树如何线性建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void sol1() {
	for(i=1; i<n; ++i) f[i]=read(), ++c[f[i]], ++c[i]; 
	for(i=1; i<=n; ++i) if(c[i]==1) break; 
	p=nw=i; 
	for(i=1; i<=n-2; ++i) {
		ans^=(i*f[nw]); c[f[nw]]--; c[nw]--; 
		if(c[f[nw]]==1 && f[nw]<p) nw=f[nw]; //极度容易错，如果父亲标号小于p，那么就让当前点为父亲
		else {
			while(c[p+1]!=1) ++p; 
			++p; nw=p; 
		}
	}
	printf("%lld", ans); 
}

注意代码中的易错点。

还原回去同理。那一行也很容易错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sol2() {
	for(i=1; i<=n-2; ++i) a[i]=read(), ++c[a[i]]; 
	for(i=1; i<=n; ++i) if(c[i]==0) break; 
	p=nw=i; 
	for(i=1; i<=n-2; ++i) {
		f[nw]=a[i]; --c[a[i]]; --c[nw]; 
		if(c[a[i]]==0 && a[i]<p) nw=a[i]; 
		else {
			while(c[p+1]!=0) ++p; 
			++p; nw=p; 
		}
	}
	f[nw]=n; 
	for(i=1; i<=n-1; ++i) ans^=(i*f[i]); 
	printf("%lld", ans); 
}

​