3866. [USACO23 Jan Platinum] Subtree Activation

【题目描述】

有一棵根为 $1$ 的树，顶点标记为 $1 \dots N$ $(2 \le N \le 2 \cdot 10^5)$ 。

每个顶点最初都处于关闭状态。

在一次操作中，你可以将一个顶点的状态从关闭状态切换到开启状态，反之亦然。

输出一个满足以下两个条件的操作序列的最小可能长度。

$\bullet$ 定义以顶点 $r$ 为根的子树由这样的顶点 $v$ 构成，使得 $r$ 位于从 $1$ 到 $v$ 的路径上 $($包括 $v)$ 。对于树的 $N$ 个子树中的每一个子树，都存在一个时刻满足：处于开启状态顶点集合中的顶点恰好都是该子树中的顶点。

$\bullet$ 在整个操作序列完成后，每个顶点都是关闭的。

【输入格式】

第一行包含 $N$ 。

第二行包含 $p_2 \dots p_N$ ， $p_i$ 是结点 $i$ 的父亲 $(1\le p_i ＜ i)$ 。

【输出格式】

输出可能的最小长度。

【样例1输入】

3
1 1

【样例1输出】

6

【样例1解释】

有三个子树，分别对应 $\{1,2,3\}、\{2\}、\{3\}$ 。下面是最小可能长度的一个操作序列。

$\bullet$ 开启 $2$ (激活的顶点形成以 $2$ 为根的子树) 。

$\bullet$ 开启 $1$ 。

$\bullet$ 开启 $3$ (激活的顶点形成以 $1$ 为根的子树) 。

$\bullet$ 关闭 $1$ 。

$\bullet$ 关闭 $2$ (激活的顶点形成以 $3$ 为根的子树) 。

$\bullet$ 关闭 $3$ 。

【样例2/3】

点击下载样例2/3

【数据规模与约定】

测试点 $1-2$ : $N \le 8$

测试点 $3-8$ : $N \le 40$

测试点 $9-14$ : $N \le 5000$

测试点 $15-20$ ：没有额外的限制。