E. Сахир и дерево с яблоками
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сахир играет со своим лучшим другом Солиманом. Он принес дерево из n вершин, пронумерованных от 1 до n, корнем дерева является вершина 1. Вершина номер i изначально содержит ai яблок. У дерева есть особенность: длина всех путей от корня к любому из листьев имеет одну и ту же четность (т.е. все пути имеют четную длину, или все пути имеют нечетную длину).

Сахир и Солиман будут ходить по очереди. Солиман будет ходить первым. Игрок, который не может сделать ход, проигрывает.

На каждом ходу текущий игрок выберет одну из вершин, возьмет ненулевое количество яблок из нее и сделает одно из следующих действий:

  1. съест эти яблоки, если вершина — лист.
  2. переместит все эти яблоки в одного из сыновей выбранной вершины, если эта вершина не является листом.

Перед тем, как Солиман сделает первых ход, Сахир сделает ровно одно изменение в дереве. А именно, он выберет две различные вершины u и v и поменяет местами яблоки в вершине u и в вершине v.

Помогите Сахиру посчитать количество способов сделать это изменение (т.е. выбрать вершины 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 таких, что если друзья начнут играть после того, как поменяют местам яблоки в этих вершинах, Сахир выиграет. (u, v) и (v, u) считаются одной и той же парой.

Примеры
Входные данные
3
2 2 3
1 1
Выходные данные
1
Входные данные
3
1 2 3
1 1
Выходные данные
0
Входные данные
8
7 2 2 5 4 3 1 1
1 1 1 4 4 5 6
Выходные данные
4
Примечание

В первом примере Сахир может выиграть только если он поменяет яблоки в вершине 1 с яблоками в вершине 3. В таком случае в обоих листьях будет по 2 яблока. Если Солиман сделает ход в листе, то Сахир сделает такой же ход в другом листе. Если Солиман передвинет яблоки из корня, то Сахир съест эти яблоки. Когда-нибудь у Солимана не будет хода.

Во втором примере нет такого изменения, чтобы Сахир выиграл.

Заметьте, что Сахир должен сделать изменение, даже если он выигрывает с изначальным деревом.