#SummerP0097. 软件包
软件包
Description
某个神秘操作系统的软件依赖可以看作是一个树形结构,Timothy 在这个系统上面已经安装了一个软件,软件需要一些前置依赖软件包,如果确定这个软件正常运行,当且仅当满足下面所有条件:
- 这个软件包没有损坏。
- 它的所有直接依赖(即其所有子节点)也都处于未损坏的状态。
可惜的是,Timothy 发现在经过滚动更新之后发现软件无法正确运行,现在他准备调查依赖是否正确;他每次操作可以选择一条链调查并修复路径上的错误,换句话说,他可以选择一个个依赖路径的终点 ,修复包括从根节点 与其简单路径上的所有依赖错误。
现在给出所有损坏的软件包,请你帮他算算,最少需要多少次操作可以修复完所有的软件错误?
*虽然众所周知依赖一般是一个 DAG 有向无环图,题目无需怀疑现实正确性
Format
Input
我们将软件包依次标号为 ,其中 1 号一定为树根。
第一行包含空格隔开的两个整数 和 ,满足 ,表示一共有 个软件包以及其中 个已经损坏。
第二行包含空格隔开的 个整数 ,满足 表示软件包 是软件包 的依赖。由于软件包 1 是树根,所以它不是任何软件包的依赖。保证给出的一定是以 1 为树根的一棵树。
第三行包含 个空格隔开的整数 满足 ,表示损坏的软件包的序号。
Output
输出最小操作次数。
Samples
5 2
1 1 2 2
2 4
1
6 3
5 5 1 1 4
2 3 4
3
Note
对于第一组样例,如图所示, 节点损坏
你只需要选择终点 从路径 修复上面的所有错误。
对于第二组样例,如图所示, 节点损坏
你需要选择终点 从路径
- ;
- ;
- ;
修复所有错误,可以证明这是最优解之一。