{"raw_statement":[{"iden":"statement","content":"Sagheer is playing a game with his best friend Soliman. He brought a tree with _n_ nodes numbered from 1 to _n_ and rooted at node 1. The _i_\\-th node has _a__i_ apples. This tree has a special property: the lengths of all paths from the root to any leaf have the same parity (i.e. all paths have even length or all paths have odd length).\n\nSagheer and Soliman will take turns to play. Soliman will make the first move. The player who can't make a move loses.\n\nIn each move, the current player will pick a single node, take a non-empty subset of apples from it and do one of the following two things:\n\n1.  eat the apples, if the node is a leaf.\n2.  move the apples to one of the children, if the node is non-leaf.\n\nBefore Soliman comes to start playing, Sagheer will make **exactly one change** to the tree. He will pick two different nodes _u_ and _v_ and swap the apples of _u_ with the apples of _v_.\n\nCan you help Sagheer count the number of ways to make the swap (i.e. to choose _u_ and _v_) after which he will win the game if both players play optimally? (_u_, _v_) and (_v_, _u_) are considered to be the same pair."},{"iden":"input","content":"The first line will contain one integer _n_ (2 ≤ _n_ ≤ 105) — the number of nodes in the apple tree.\n\nThe second line will contain _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 107) — the number of apples on each node of the tree.\n\nThe third line will contain _n_ - 1 integers _p_2, _p_3, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — the parent of each node of the tree. Node _i_ has parent _p__i_ (for 2 ≤ _i_ ≤ _n_). Node 1 is the root of the tree.\n\nIt is guaranteed that the input describes a valid tree, and the lengths of all paths from the root to any leaf will have the same parity."},{"iden":"output","content":"On a single line, print the number of different pairs of nodes (_u_, _v_), _u_ ≠ _v_ such that if they start playing after swapping the apples of both nodes, Sagheer will win the game. (_u_, _v_) and (_v_, _u_) are considered to be the same pair."},{"iden":"examples","content":"Input\n\n3\n2 2 3\n1 1\n\nOutput\n\n1\n\nInput\n\n3\n1 2 3\n1 1\n\nOutput\n\n0\n\nInput\n\n8\n7 2 2 5 4 3 1 1\n1 1 1 4 4 5 6\n\nOutput\n\n4"},{"iden":"note","content":"In the first sample, Sagheer can only win if he swapped node 1 with node 3. In this case, both leaves will have 2 apples. If Soliman makes a move in a leaf node, Sagheer can make the same move in the other leaf. If Soliman moved some apples from a root to a leaf, Sagheer will eat those moved apples. Eventually, Soliman will not find a move.\n\nIn the second sample, There is no swap that will make Sagheer win the game.\n\nNote that Sagheer must make the swap even if he can win with the initial tree."}],"translated_statement":[{"iden":"statement","content":"Sagheer 正在和他的好朋友 Soliman 玩一个游戏。他带来了一棵包含 #cf_span[n] 个节点的树，节点编号从 #cf_span[1] 到 #cf_span[n]，根节点为 #cf_span[1]。第 #cf_span[i] 个节点上有 #cf_span[ai] 个苹果。这棵树有一个特殊性质：从根节点到任意叶子节点的所有路径长度具有相同的奇偶性（即所有路径长度均为偶数，或所有路径长度均为奇数）。\n\nSagheer 和 Soliman 将轮流进行游戏，Soliman 先手。无法进行移动的玩家输掉游戏。\n\n在每一轮移动中，当前玩家会选择一个节点，从中取出一个非空子集的苹果，然后执行以下两种操作之一：\n\n在 Soliman 开始游戏前，Sagheer 将对树进行 *恰好一次* 修改。他会选择两个不同的节点 #cf_span[u] 和 #cf_span[v]，并将这两个节点上的苹果数量互换。\n\n你能帮助 Sagheer 计算有多少种交换方式（即选择 #cf_span[u] 和 #cf_span[v]）使得在双方都采取最优策略的情况下，Sagheer 能赢得游戏吗？#cf_span[(u, v)] 和 #cf_span[(v, u)] 被视为同一对。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 10^5]）——苹果树的节点数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^7]）——树上每个节点的苹果数量。\n\n第三行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——树上每个节点的父节点。节点 #cf_span[i] 的父节点为 #cf_span[pi]（对于 #cf_span[2 ≤ i ≤ n]）。节点 #cf_span[1] 是树的根。\n\n保证输入描述的是一棵合法的树，且从根节点到任意叶子节点的所有路径长度具有相同的奇偶性。\n\n请在一行中输出满足以下条件的不同节点对 #cf_span[(u, v)]（#cf_span[u ≠ v]）的数量：在交换节点 #cf_span[u] 和 #cf_span[v] 上的苹果后，若双方都采取最优策略，Sagheer 将赢得游戏。#cf_span[(u, v)] 和 #cf_span[(v, u)] 被视为同一对。\n\n在第一个样例中，Sagheer 只有在交换节点 #cf_span[1] 和节点 #cf_span[3] 时才能获胜。此时，两个叶子节点都各有 #cf_span[2] 个苹果。如果 Soliman 在某个叶子节点上操作，Sagheer 可以在另一个叶子节点上做出相同的操作；如果 Soliman 从根节点向叶子节点移动了一些苹果，Sagheer 将吃掉这些被移动的苹果。最终，Soliman 将无法进行任何移动。\n\n在第二个样例中，不存在任何交换能使 Sagheer 获胜。\n\n请注意：即使初始树已经能让 Sagheer 获胜，他也必须进行一次交换。"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 10^5]）——苹果树的节点数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 10^7]）——树上每个节点的苹果数量。\n\n第三行包含 #cf_span[n - 1] 个整数 #cf_span[p2, p3, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——树上每个节点的父节点。节点 #cf_span[i] 的父节点为 #cf_span[pi]（对于 #cf_span[2 ≤ i ≤ n]）。节点 #cf_span[1] 是树的根。\n\n保证输入描述的是一棵合法的树，且从根节点到任意叶子节点的所有路径长度具有相同的奇偶性。"},{"iden":"output","content":"请在一行中输出满足以下条件的不同节点对 #cf_span[(u, v)]（#cf_span[u ≠ v]）的数量：在交换节点 #cf_span[u] 和 #cf_span[v] 上的苹果后，若双方都采取最优策略，Sagheer 将赢得游戏。#cf_span[(u, v)] 和 #cf_span[(v, u)] 被视为同一对。"},{"iden":"examples","content":"输入：\n3\n2 2 3\n1 1\n输出：\n1\n\n输入：\n3\n1 2 3\n1 1\n输出：\n0\n\n输入：\n8\n7 2 2 5 4 3 1 1\n1 1 1 4 4 5 6\n输出：\n4"},{"iden":"note","content":"在第一个样例中，Sagheer 只有在交换节点 #cf_span[1] 和节点 #cf_span[3] 时才能获胜。此时，两个叶子节点都各有 #cf_span[2] 个苹果。如果 Soliman 在某个叶子节点上操作，Sagheer 可以在另一个叶子节点上做出相同的操作；如果 Soliman 从根节点向叶子节点移动了一些苹果，Sagheer 将吃掉这些被移动的苹果。最终，Soliman 将无法进行任何移动。\n\n在第二个样例中，不存在任何交换能使 Sagheer 获胜。\n\n请注意：即使初始树已经能让 Sagheer 获胜，他也必须进行一次交换。"}],"sample_group":[],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}