Subtree Activation

题目描述

为了庆祝新年，Bessie 和她的朋友们搭建了一棵巨大的树，上面挂着许多会发光的装饰品。Bessie 可以通过遥控器将装饰品打开或关闭。在日出之前，她想按某种顺序切换一些装饰品的状态（可能会对同一个装饰品切换多次），使得整棵树在开始和结束时都没有任何装饰品处于开启状态。

Bessie 觉得，当被激活的装饰品集合恰好是以某个顶点为根的一棵子树时，树看起来很酷。她希望切换装饰品的顺序满足：对于树上的每一棵子树，在某个时刻，开启状态的顶点集合恰好等于这棵子树的所有顶点。此外，打开和关闭装饰品需要能量，Bessie 不想浪费能量，因此她想找到最少的切换次数。

形式化地，给定一棵以 $1$ 为根的树，顶点标号为 $1\dots N$（$2\le N\le 2\cdot 10^5$）。每个顶点初始为未激活状态。一次操作中，你可以将某个顶点的状态从未激活切换为激活，或从激活切换为未激活。请输出满足以下两个条件的操作序列的最小可能长度：

定义以顶点 $r$ 为根的子树为所有满足 $r$ 位于从 $1$ 到 $v$ 的路径上（含端点）的顶点 $v$ 的集合。对于这棵树的 $N$ 个子树中的每一个，都存在某个时刻，使得激活顶点的集合恰好等于该子树中的所有顶点。

在整个操作序列结束后，每个顶点都为未激活状态。

输入格式

第一行包含 $N$。 第二行包含 $p_2 \dots p_N$（$1\le p_i<i$），其中 $p_i$ 表示顶点 $i$ 在树中的父节点。

输出格式

输出最小可能的长度。

3
1 1

6

提示

共有三棵子树，分别对应于 $\{1,2,3\}$、$\{2\}$ 和 $\{3\}$。 下面是一种达到最小长度的操作序列： 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. Problem credits: Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum