题目描述

题目译自 USACO 2023 January Contest, Platinum Problem 3. Subtree Activation

为了庆祝新年，Bessie 和她的朋友们建造了一棵巨大的树，上面有许多发光的彩灯。Bessie 可以通过遥控来打开和关闭这些灯。在太阳升起之前，她想按一定的顺序开关一些灯（可能一盏灯要开关一次以上），使得开始和结束时树上都没有亮的灯。Bessie 认为，如果亮的灯的集合正好是以某个顶点为根的子树，那么这棵树看起来就很酷。她希望她开关的灯的顺序能满足这样一个属性：对于每一棵子树，在某个时间点，它正好是所有亮的灯的集合。此外，开关灯需要能量，Bessie 不想浪费能量，所以她想找到她能执行的最小的开关次数。

形式化地，有一棵 $N$ 个节点的树，节点编号为 $1\ldots N$，根为节点 $1$。每个节点最初都是未被激活的。一次操作中，你可以翻转一个节点的状态（从未激活变为已激活，反之亦然）。输出满足如下两个条件的最短操作序列的长度：

• 定义以节点 $r$ 为根的子树由所有满足 $r$ 位于 $1$ 到 $v$ 的路径上（包括两端）的节点 $v$ 组成。对于这棵树的 $N$ 棵子树中的每一棵，都存在一个时刻，满足已激活的顶点集合恰好是这棵子树的点集。
• 在结束所有操作后所有节点都是未被激活的。

输入格式

第一行一个整数 $N\ (2\le N\le 2\cdot 10^5)$。

第二行包含 $p_2,\ldots,p_N\ (1\le p_i<i)$，其中 $p_i$ 表示树上节点 $i$ 的父节点。

输出格式

输出最小可能长度。

3
1 1

6

数据范围与提示

• 2-3 组数据：$N\le 8$
• 4-9 组数据：$N\le 40$
• 10-15 组数据：$N\le 5000$
• 16-21 组数据：无附加限制