P9021 [USACO23JAN] Subtree Activation P

题目描述

你有一棵根为 $1$ 的树，顶点标记为 $1 \dots N$ $(2 \le N \le 2 \cdot 10^5)$ 。每个顶点最初都是关闭的。在一次操作中，你可以将一个顶点的状态从关闭状态切换到开启状态，反之亦然。输出一个满足以下两个条件的操作序列的最小可能长度。

• 定义以顶点 $r$ 为根的子树由所有满足 $r$ 位于从 $1$ 到 $v$ 的路径上 $($包括 $v)$ , 的顶点 $v$ 组成。每一个顶点的子树，都有一个时刻，开启状态顶点的集合恰好是该子树中的顶点。
• 在整个操作序列之后，每个顶点都是关闭的。

输入格式

第一行包含 $N$ 。

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

输出格式

输出可能的最小长度。

输入输出样例 1

3
1 1

6

说明/提示

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

• 开启 $2$ (激活的顶点形成以 $2$ 为根的子树) 。
• 开启 $1$ 。
• 开启 $3$ (激活的顶点形成以 $1$ 为根的子树) 。
• 关闭 $1$ 。
• 关闭 $2$ (激活的顶点形成以 $3$ 为根的子树) 。
• 关闭 $3$ 。

子任务：

• 测试点 $2-3$ : $N \le 8$
• 测试点 $4-9$ : $N \le 40$
• 测试点 $10-15$ : $N \le 5000$
• 测试点 $16-21$ ：没有额外的限制。