← 返回题目列表

Codeforces · 812/E

E. 萨吉尔和苹果树

中文机器翻译题面 查看原题

Sagheer 正在和他最好的朋友 Soliman 玩游戏。他带来了一棵有 n 个节点的树,编号从 1 到 n,以节点 1 为根。第 i 个节点有 ai 个苹果。这棵树有一个特殊的属性:从根到任何叶子的所有路径的长度都具有相同的奇偶性(即所有路径具有偶数长度或所有路径具有奇数长度)。

Sagheer 和 Soliman 将轮流上场。索利曼将迈出第一步。无法采取行动的玩家就输了。

在每次移动中,当前玩家将选择一个节点,从中取出苹果的非空子集,并执行以下两件事之一:

1. 如果节点是叶子,则吃苹果。
2. 如果该节点是非叶节点,则将苹果移至其中一个子节点。

在 Soliman 开始比赛之前,Sagheer 将对树进行一项更改。他将选择两个不同的节点 u 和 v,并将 u 的苹果与 v 的苹果交换。

你能帮助 Sagheer 数一下进行交换的方法(即选择 u 和 v),如果双方都发挥最佳,他将赢得比赛吗? (u, v) 和 (v, u) 被认为是同一对。

输入

第一行将包含一个整数 n (2 ≤ n ≤ 105) — 苹果树中的节点数。

第二行将包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 107) — 树的每个节点上的苹果数量。

第三行将包含 n - 1 个整数 p2, p3, ..., pn (1 ≤ pi ≤ n) — 树的每个节点的父节点。节点 i 具有父节点 pi(对于 2 ≤ i ≤ n)。节点 1 是树的根。

保证输入描述一棵有效的树,并且从根到任何叶子的所有路径的长度将具有相同的奇偶校验。

输出

在一行上,打印不同节点对 (u, v) 的数量,u ≠ v,这样如果他们在交换两个节点的苹果后开始玩,Sagheer 将赢得游戏。 (u, v) 和 (v, u) 被认为是同一对。

示例

输入 #1

3
2 2 3
1 1

输出 #1

1

输入 #2

3
1 2 3
1 1

输出 #2

0

输入 #3

8
7 2 2 5 4 3 1 1
1 1 1 4 4 5 6

输出 #3

4

注意

在第一个示例中,Sagheer 只有将节点 1 与节点 3 交换才能获胜。在这种情况下,两个叶子都会有 2 个苹果。如果 Soliman 在一个叶节点中进行了移动,Sagheer 可以在另一个叶节点中进行相同的移动。如果索利曼将一些苹果从根移到叶子上,萨吉尔就会吃掉那些移动的苹果。最终,索利曼将找不到出路。

在第二个示例中,没有任何交换可以使 Sagheer 赢得比赛。

请注意,即使 Sagheer 可以用初始树获胜,他也必须进行交换。