Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).
Напомним, что простой путь — это путь, посещающий каждую вершину не более одного раза. Назовем весом пути побитовое исключающее ИЛИ значений записанных на его вершинах. Скажем, что дерево хорошее, если в нем не существует ни одного простого пути с весом \(0\).
Вы можете применить следующую операцию произвольное количество раз (возможно, ноль): выбрать вершину дерева и заменить значение записанное на ней на произвольное положительное целое число. Какое минимальное количество раз необходимо применить данную операцию, чтобы дерево стало хорошим?
В первой строке задано целое число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) — количество вершин.
Во второй строке задано \(n\) целых чисел \(a_1\), \(a_2\), ..., \(a_n\) (\(1 \le a_i < 2^{30}\)) — числа, записанные на вершинах дерева.
Затем следует \(n - 1\) строка, каждая из которых содержит два числа \(x\) и \(y\) (\(1 \le x, y \le n; x \ne y\)), обозначающие ребро между вершиной \(x\) и вершиной \(y\). Гарантируется, что эти ребра задают дерево.
Выведите одно целое число — минимальное количество раз, которое необходимо применить операцию, чтобы дерево стало хорошим.
В первом примере можно заменить значение на вершине \(1\) на \(13\), а значение на вершине \(4\) — на \(42\).
6 3 2 1 3 2 1 4 5 3 4 1 4 2 1 6 1
2
4 2 1 1 1 1 2 1 3 1 4
0
5 2 2 2 2 2 1 2 2 3 3 4 4 5
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач