题目描述
在被先后两任新生舞会舞伴以当天有事为由抛弃后,Bronya18C 决定加训算法竞赛。
这天 Bronya18C 在加训的时候遇到了这样一道题目:
给定一个有根树森林,两位玩家 Bronya18C 和 Bronya19C 轮流操作,Bronya18C 先手。
每次操作开始时,若森林为空,则当前玩家输掉游戏。
否则当前玩家需要选择一个节点 u,并删去 u 所在的连通块的根 r 到节点 u 的唯一简单路径上的所有节点,以及与这些节点相邻的边。
操作后新产生的连通块的根为该连通块中原先到 r 距离最小的节点。
显然 Bronya18C 和 Bronya19C 都绝顶聪明,你需要判断当两位玩家都采取最优策略时谁会获胜。
由于这是 IOI 赛制,为了证明你真的会做这道题,你还需要求出初始局面的 SG 值[^1]。
退役太久的 Bronya18C 发现自己已经不会写代码了,请你帮帮他!
输入格式
第一行输入一个正整数 T 表示有根树森林的连通块个数。
接下来依次输入 T 棵有根树,每棵有根树按如下格式输入:
第一行输入一个正整数 n 表示有根树的节点数,节点由 1 到 n 编号,有根树以节点 1 为根。
若 n≠1,接下来一行输入 n−1 个正整数,第 i 个正整数表示节点 i+1 在有根树上的父亲 pi+1。
输出格式
输出一行一个整数表示初始局面的 SG 值。
样例输入 1
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
样例输出 1
9
样例输入 2 ~ 5
见下发文件 sample2.in
、sample3.in
、sample4.in
、sample5.in
,分别满足子任务 1、2、3、4 的限制。
样例输出 2 ~ 5
见下发文件 sample2.ans
、sample3.ans
、sample4.ans
、sample5.ans
。
数据范围
记 ∑n 为有根树森林的总节点数。
对于所有测试点,1≤∑n≤2×106,1≤pi<i。
子任务编号 | ∑n≤ | 特殊性质 | 分数 |
---|---|---|---|
1 | 5000 | 无 | 10 |
2 | 2×106 | pi 在 [1,i−1]∩Z 中均匀随机 | 10 |
3 | 2×105 | 无 | 30 |
4 | 2×106 | 50 |
[^1]: OI Wiki - 有向图游戏与 SG 函数