CF812E Sagheer and Apple Tree

Sagheer 正在和他最好的朋友 Soliman 玩一个游戏。他带来了一棵有 $n$ 个结点的树，结点编号从 $1$ 到 $n$，树的根为结点 $1$。第 $i$ 个结点上有 $a_{i}$ 个苹果。这棵树有一个特殊的性质：从根到任意叶子的所有路径的长度的奇偶性相同，也就是说所有路径要么都是偶数长度，要么都是奇数长度。 Sagheer 和 Soliman 轮流进行游戏，Soliman 先手。无法进行操作的玩家输掉比赛。 每一回合，当前玩家可以选择任意一个结点，从其中取出一个非空的苹果子集，然后执行以下两种操作之一： 1. 如果这个结点是叶子结点，则吃掉这些苹果。 2. 如果这个结点不是叶子结点，则将这些苹果移到它的某个子结点中。 在 Soliman 开始游戏之前，Sagheer 允许进行一次操作。他可以选择两个不同的结点 $u$ 和 $v$，将 $u$ 和 $v$ 结点上的苹果数量进行交换。 请你帮助 Sagheer 统计有多少种交换方法（即选择 $u$ 和 $v$ 的方式），使得双方都采取最优策略后，Sagheer 能赢得这场游戏。$(u,v)$ 与 $(v,u)$ 被视为相同的一对。

第一行包含一个整数 $n$（$2 \leq n \leq 10^{5}$），表示苹果树的结点数。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^{7}$），表示每个结点上的苹果数。 第三行包含 $n-1$ 个整数 $p_{2},p_{3},...,p_{n}$（$1 \leq p_{i} \leq n$），表示每个结点的父节点编号（对于 $2 \leq i \leq n$）。结点 $1$ 是树根。 保证输入描述的是一棵合法的树，并且从根到任意叶子的所有路径长度具有相同的奇偶性。

输出一行，表示有多少种不同的结点对 $ (u,v) $，$u \neq v$，满足交换它们的苹果后，如果双方都采取最优策略，Sagheer 能获胜。$(u,v)$ 与 $(v,u)$ 被认为是同一对。

在第一个样例中，Sagheer 只有在将结点 $1$ 和结点 $3$ 的苹果交换后才能获胜。此时，两个叶子节点都拥有 2 个苹果。如果 Soliman 在任意一个叶子上采取行动，Sagheer 可以在另一个叶子上采取相同的行动。如果 Soliman 选择将苹果从根节点移动到叶子，Sagheer 就可以吃掉移动到叶子的苹果。最终，Soliman 会无法操作。 在第二个样例中，没有任何一次交换能够让 Sagheer 获胜。 注意，即使初始情况下 Sagheer 能获胜，他也必须进行一次交换操作。 由 ChatGPT 5 翻译