Prufer序列

Prufer性质

Prufer数列是无根树的一种数列。在组合数学中，Prufer数列由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的Prufer数列长度为n-2
1.若编号i在Prufer序列出现cnt次，那么它在的度数为cnt+1
2.n个点无标号无根树的形态有n^n-2种
3.n个点有标号无根树形态有：
4：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e6 + 50;
typedef long long LL;
LL N, M, Ans = 0, father[MAXN], Prufer[MAXN], du[MAXN];//father数组即题目中的f数组
LL read() {
    //快读
	LL cnt = 0, flag = 1;
	char c = getchar();
	while (c < '0' || c>'9') {
     if (c == '-') flag = -1; c = getchar(); }
	while (c >= '0' && c <= '9') cnt = (cnt << 1) + (cnt << 3) + (c ^ 48), c = getchar();
	return flag * cnt;
}
void Tree_to_Prufer() {
    
	for (int i = 1; i <= N - 1; i++) father[i] = read(), du[father[i]]++;//将父节点的度加一
	for (int i = 1, now = 1; i <= N - 1; i++, now++) {
    
		while (du[now]) now++;//找到编号最小的叶节点
		Prufer[i] = father[now];//加入Prufer序列
		while (i < N - 2 && !--du[Prufer[i]] && Prufer[i] < now) Prufer[i + 1] = father[Prufer[i]], i++;//当父亲节点编号较小时，继续将父亲节点加入Prufer序列
	}
	for (int i = 1; i <= N - 2; i++) Ans ^= i * Prufer[i];//计算权值
}
void Prufer_to_Tree() {
    
	for (int i = 1; i <= N - 2; i++) Prufer[i] = read(), du[Prufer[i]]++;//将父节点的度加一
	Prufer[N - 1] = N;//这里需要特别注意一下
	for (int i = 1, now = 1; i <= N - 1; i++, now++) {
    
		while (du[now]) now++;//找到编号最小的叶节点
		father[now] = Prufer[i];//加入父亲数组
		while (i < N - 1 && !--du[Prufer[i]] && Prufer[i] < now) father[Prufer[i]] = Prufer[i + 1], i++;//当父亲节点编号较小时，继续将父亲节点加入父亲数组
	}
	for (int i = 1; i <= N - 1; i++) Ans ^= i * father[i];//计算权值
}
int main() {
    
	memset(du, 0, sizeof(du));
	N = read(); M = read();
	if (M == 1) Tree_to_Prufer();
	else Prufer_to_Tree();
	printf("%lld\n", Ans);
	return 0;
}