题目描述

For the New Year celebration, Bessie and her friends have constructed a giant tree with many glowing ornaments. Bessie has the ability to turn the ornaments on and off through remote control. Before the sun rises, she wants to toggle some of the ornaments in some order (possibly toggling an ornament more than once) such that the tree starts and ends with no ornaments on. Bessie thinks the tree looks cool if the set of activated ornaments is exactly a subtree rooted at some vertex. She wants the order of ornaments she toggles to satisfy the property that, for every subtree, at some point in time it was exactly the set of all turned on ornaments. Additionally, it takes energy to switch on and off ornaments, and Bessie does not want to waste energy, so she wants to find the minimum number of toggles she can perform.

Formally, you have a tree with vertices labeled $1 \cdots N (2 \le N \le 2 \cdot 10^5)$ rooted at $1$. Each vertex is initially inactive. In one operation, you can toggle the state of a single vertex from inactive to active or vice versa. Output the minimum possible length of a sequence of operations satisfying both of the following conditions:

• Define the subtree rooted at a vertex $r$ to consist of all vertices $v$ such that $r$ lies on the path from $1$ to $v$ inclusive. For every one of the $N$ subtrees of the tree, there is a moment in time when the set of active vertices is precisely those in that subtree.
• Every vertex is inactive after the entire sequence of operations.

输入格式

The first line contains $N$.

The second line contains $p_2 \cdots p_N (1 \le p_i<i)$, where $p_i$ denotes the parent of vertex $i$ in the tree.

输出格式

Output the minimum possible length.

题目大意

题目描述

你有一棵根为 $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,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$ ：没有额外的限制。

3
1 1

6

提示

Explanation for Sample 1

There are three subtrees, corresponding to $\{1,2,3\}$, $\{2\}$, and $\{3\}$. Here is one sequence of operations of the minimum possible length:

activate 2
(activated vertices form the subtree rooted at 2)
activate 1
activate 3
(activated vertices form the subtree rooted at 1)
deactivate 1
deactivate 2
(activated vertices form the subtree rooted at 3)
deactivate 3

Scoring

• Inputs $2-3$: $N \le 8$
• Inputs $4-9$: $N \le 40$
• Inputs $10-15$: $N \le 5000$
• Inputs $16-21$: No additional constraints.