比赛场次 576
比赛名称 4043级2023省选模拟赛7
比赛状态 已结束比赛成绩
开始时间 2023-03-29 08:00:00
结束时间 2023-03-29 12:30:00
开放分组 全部用户
注释介绍 春风十里,好题
题目名称 Subtree Activation
输入输出 shujihuo.in/out
时间限制 2000 ms (2 s)
内存限制 256 MiB
测试点数 20 简单对比
用户 结果 时间 内存 得分
Gravatarop_组撒头屯 AAAAAAAAAAAAAAAAAAAA
0.223 s 3.55 MiB 100
Gravatarムラサメ WWWAAAWWAWWWWWWWWWWW
0.000 s 0.00 MiB 20

Subtree Activation

★★★★   输入文件:shujihuo.in   输出文件:shujihuo.out   简单对比
时间限制:2 s   内存限制:256 MiB

【题目描述】

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