【模板】Prufer 序列(Prufer Sequence)

题目描述

Prüfer 序列又写作 Prufer 序列。

请实现 Prüfer 序列和无根树的相互转化。

为方便你实现代码，尽管是无根树，我们在读入时仍将 $n$ 设为其根。

对于一棵无根树，设 $f_{1\dots n-1}$ 为其父亲序列（$f_i$ 表示 $i$ 在 $n$ 为根时的父亲），设 $p_{1 \dots n-2}$ 为其 Prüfer 序列。

另外，对于一个长度为 $m$ 的序列 $a_{1 \dots m}$，我们设其权值为 $\operatorname{xor}_{i = 1}^m i \times a_i$。

输入格式

第一行两个整数 $n,m$，表示树的点数和转化类型。

若 $m = 1$，第二行一行 $n-1$ 个整数，表示父亲序列。
若 $m = 2$，第二行一行 $n-2$ 个整数，表示 Prüfer 序列。

输出格式

若 $m = 1$，一行一个整数，表示给出的父亲序列对应的 Prüfer 序列的权值。
若 $m = 2$，一行一个整数，表示给出的 Prüfer 序列对应的父亲序列的权值。

样例输入 #1

6 1
3 6 4 6 1

样例输出 #1

29

样例输入 #2

6 2
4 6 5 2

样例输出 #2

4

数据范围

【样例 1 解释】

$p = \{6\ 1\ 3\ 4\}$。

【样例 2 解释】

$f = \{4\ 6\ 6\ 5\ 2\}$。

【数据范围】

知识点与难度

本题涉及的知识点从属于 NOI，难度（CF Rating）：2100。

测试点分布

出处：原题链接