#1045. 游戏时间

内存限制:512 MiB 时间限制:2000 ms 输入文件:game.in 输出文件:game.out
题目类型:传统 评测方式:文本比较
上传者: H6_6Q

题目描述

小P 和 小G 在一张地图上玩游戏,可是 小G 总是输,由于 小G 气急败坏,决定通过作弊来赢得游戏的胜利。

游戏地图有 n 个地点,依次将他们编号为 1,2\ ...\ n ,有 n-1 条道路将这些地点相连,且每两个地点之间都能互相到达。

现在地图将这些点分为了 生产地点加工地点 两种,每个地点都对应着这两种地点中的其中的一种。

这场游戏分为选择阶段,发展阶段,竞争阶段等几个部分。

而这场游戏中选择阶段的规则是:

  • 由先手开始,每轮的操作者可以选择一个没有被选过的 生产地点加工地点

  • 把能由该节点沿着道路出发且只通过与该地点类型相同的地点时能到达的所有地点作为自己的地点选下。

由于这张游戏地图是 小P 给出的,所以他作为游戏的先手的进行操作。

小G 已经谋划好了选地后的操作使自己胜利,而 小G 计划的前提是不论两人怎么取,小G 都至少要选择 \bigg\lfloor \dfrac{n}{2} \bigg\rfloor 次地点才能实施,可是地图上的地点可能无法让他选择 \bigg\lfloor \dfrac{n}{2} \bigg\rfloor 次。

小G 为了实施他的计划来取得胜利,决定偷偷修改地图上某些地点的类型。每次他可以选择任意一个地点,将这个地点的类型修改为他想要的那个类型。

小G 为了尽可能地不让 小P 发现自己的行为而受到嘲笑,便希望用最少的修改次数来实现他的目标。可他不会算这个最小的修改次数,请你替他求出这个修改次数的最小值。

一句话题意:每次可以反转一个点的权值,用最少的修改次数使得树上所有相邻的节点的权值不同。

输入格式

第一行输入一个 n ,表示地图上地点的个数。

第二行输入 n 个整数 a_i ,每个整数都是 0 1
a_i 0 则表示地点 i 生产地点 ,否则为 加工地点

接下来一行输入 n-1 个整数,第 i 个整数 p_i 表示点 i+1 与点 p_i 之间连有一条边。

输出格式

输出一个整数,表示 小G 达到目的所需要的最少修改次数。

若 小G 无论如何也无法达到他的目的,则输出 -1

样例

输入样例 #1:

5
1 0 1 0 1
1 1 3 3

输出样例 #1:

2

数据范围与提示

【样例解释】

修改 3 号节点和 4 号节点即可满足条件。

【数据范围与约定】

对于 50\% 的数据, 1 \le n \le 10^3

对于 80\% 的数据, 1 \le n \le 10^5

对于全部数据: 1 \le n \le 10^7 a_i \in \left\{0,1\right\} 1 \le x,y \le n p_i \le i