A6160. 「USACO 2023.1 Platinum」Subtree Activation
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 January Contest, Platinum](http://usaco.org/index.php?page=jan23results) Problem 3. [Subtree Activation](http://usaco.org/index.php?page=viewproblem2&cpid=1286)**
为了庆祝新年，Bessie 和她的朋友们建造了一棵巨大的树，上面有许多发光的彩灯。Bessie 可以通过遥控来打开和关闭这些灯。在太阳升起之前，她想按一定的顺序开关一些灯（可能一盏灯要开关一次以上），使得开始和结束时树上都没有亮的灯。Bessie 认为，如果亮的灯的集合正好是以某个顶点为根的子树，那么这棵树看起来就很酷。她希望她开关的灯的顺序能满足这样一个属性：对于每一棵子树，在某个时间点，它正好是所有亮的灯的集合。此外，开关灯需要能量，Bessie 不想浪费能量，所以她想找到她能执行的最小的开关次数。
形式化地，有一棵 $N$ 个节点的树，节点编号为 $1\ldots N$，根为节点 $1$。每个节点最初都是未被激活的。一次操作中，你可以翻转一个节点的状态（从未激活变为已激活，反之亦然）。输出满足如下两个条件的最短操作序列的长度：
- 定义以节点 $r$ 为根的子树由所有满足 $r$ 位于 $1$ 到 $v$ 的路径上（包括两端）的节点 $v$ 组成。对于这棵树的 $N$ 棵子树中的每一棵，都存在一个时刻，满足已激活的顶点集合恰好是这棵子树的点集。
- 在结束所有操作后所有节点都是未被激活的。
为了庆祝新年，Bessie 和她的朋友们建造了一棵巨大的树，上面有许多发光的彩灯。Bessie 可以通过遥控来打开和关闭这些灯。在太阳升起之前，她想按一定的顺序开关一些灯（可能一盏灯要开关一次以上），使得开始和结束时树上都没有亮的灯。Bessie 认为，如果亮的灯的集合正好是以某个顶点为根的子树，那么这棵树看起来就很酷。她希望她开关的灯的顺序能满足这样一个属性：对于每一棵子树，在某个时间点，它正好是所有亮的灯的集合。此外，开关灯需要能量，Bessie 不想浪费能量，所以她想找到她能执行的最小的开关次数。
形式化地，有一棵 $N$ 个节点的树，节点编号为 $1\ldots N$，根为节点 $1$。每个节点最初都是未被激活的。一次操作中，你可以翻转一个节点的状态（从未激活变为已激活，反之亦然）。输出满足如下两个条件的最短操作序列的长度：
- 定义以节点 $r$ 为根的子树由所有满足 $r$ 位于 $1$ 到 $v$ 的路径上（包括两端）的节点 $v$ 组成。对于这棵树的 $N$ 棵子树中的每一棵，都存在一个时刻，满足已激活的顶点集合恰好是这棵子树的点集。
- 在结束所有操作后所有节点都是未被激活的。
输入格式
第一行一个整数 $N\ (2\le N\le 2\cdot 10^5)$。
第二行包含 $p_2,\ldots,p_N\ (1\le p_i<i)$，其中 $p_i$ 表示树上节点 $i$ 的父节点。
第二行包含 $p_2,\ldots,p_N\ (1\le p_i<i)$，其中 $p_i$ 表示树上节点 $i$ 的父节点。
输出格式
输出最小可能长度。
输入输出样例
输入 #1
3 1 1
输出 #1
6
说明/提示
- 2-3 组数据：$N\le 8$
- 4-9 组数据：$N\le 40$
- 10-15 组数据：$N\le 5000$
- 16-21 组数据：无附加限制
- 4-9 组数据：$N\le 40$
- 10-15 组数据：$N\le 5000$
- 16-21 组数据：无附加限制