新生舞会 - Problem

在被先后两任新生舞会舞伴以当天有事为由抛弃后，Bronya18C 决定加训算法竞赛。

这天 Bronya18C 在加训的时候遇到了这样一道题目：

给定一个有根树森林，两位玩家 Bronya18C 和 Bronya19C 轮流操作，Bronya18C 先手。

每次操作开始时，若森林为空，则当前玩家输掉游戏。

否则当前玩家需要选择一个节点 $u$，并删去 $u$ 所在的连通块的根 $r$ 到节点 $u$ 的唯一简单路径上的所有节点，以及与这些节点相邻的边。

操作后新产生的连通块的根为该连通块中原先到 $r$ 距离最小的节点。

显然 Bronya18C 和 Bronya19C 都绝顶聪明，你需要判断当两位玩家都采取最优策略时谁会获胜。

由于这是 IOI 赛制，为了证明你真的会做这道题，你还需要求出初始局面的 SG 值[^1]。

退役太久的 Bronya18C 发现自己已经不会写代码了，请你帮帮他！

第一行输入一个正整数 $T$ 表示有根树森林的连通块个数。

接下来依次输入 $T$ 棵有根树，每棵有根树按如下格式输入：

第一行输入一个正整数 $n$ 表示有根树的节点数，节点由 $1$ 到 $n$ 编号，有根树以节点 $1$ 为根。

若 $n \neq 1$，接下来一行输入 $n - 1$ 个正整数，第 $i$ 个正整数表示节点 $i + 1$ 在有根树上的父亲 $p_{i + 1}$。

输出一行一个整数表示初始局面的 SG 值。

10
1
2
1
3
1 2
4
1 1 2
5
1 2 2 1
6
1 1 3 3 5
7
1 2 1 3 5 6
8
1 1 2 2 3 3 5
9
1 2 3 3 2 3 5 6
10
1 2 3 3 2 3 2 6 1

见下发文件 sample2.in 、sample3.in、sample4.in、sample5.in，分别满足子任务 1、2、3、4 的限制。

见下发文件 sample2.ans、sample3.ans、sample4.ans、sample5.ans。

记 $\sum n$ 为有根树森林的总节点数。

对于所有测试点，$1 \le \sum n \le 2 \times 10^6, 1 \le p_i < i$。

子任务编号	$\sum n \le$	特殊性质	分数
1	5000	无	10
2	$2 \times 10^6$	$p_i$ 在 $[1, i - 1] \cap \mathbb{Z}$ 中均匀随机	10
3	$2 \times 10^5$	无	30
4	$2 \times 10^6$	无	50

QOJ.ac