Prufer sequence

Prufer性质

Prufer数列是无根树的一种数列.在组合数学中,Prufer数列由有一个对于顶点标过号的树转化来的数列,点数为n的树转化来的Prufer数列长度为n-2
1.若编号i在Prufersequence appearscnt次,Then it is in degreescnt+1
2.nThe shape of a point unlabeled unrooted tree hasn^n-2种
3.nEach point has a labelled unrooted tree shape：
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];//fatherThe array is in the titlef数组
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]]++;//Increase the degree of the parent node by one
	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++;//When the parent node number is smaller,Continue to add the parent nodePrufer序列
	}
	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]]++;//Increase the degree of the parent node by one
	Prufer[N - 1] = N;//这里需要特别注意一下
	for (int i = 1, now = 1; i <= N - 1; i++, now++) {
    
		while (du[now]) now++;//找到编号最小的叶节点
		father[now] = Prufer[i];//Join the parent array
		while (i < N - 1 && !--du[Prufer[i]] && Prufer[i] < now) father[Prufer[i]] = Prufer[i + 1], i++;//When the parent node number is smaller,Continue adding the parent node to the parent array
	}
	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;
}