Задача №115158. Самостоятельные деревья
Дано дерево (связный граф с \(n\) вершинами и \(n-1\) ребрами), в каждой вершине которого находится неотрицательное целое число. Назовём дерево самостоятельным , если побитовое исключающее ИЛИ всех чисел в его вершинах равно \(0\). Вам нужно найти, на какое максимальное количество самостоятельных деревьев можно разбить изначальное дерево, или сказать, что разбить изначальное дерево на самостоятельные деревья невозможно.
Разбиение дерева — это удаление из него нескольких рёбер. Можно показать, что в результате такой операции граф превратится в несколько непересекающихся деревьев.
Исключающее ИЛИ — это логическая операция, обозначаемая знаком \(\oplus\), которая задаётся следующей таблицей истинности:
| \(x\) | \(y\) | \(x \oplus y\) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Побитовое исключающее ИЛИ двух неотрицательных целых чисел \(x\) и \(y\) тоже обозначается \(x \oplus y\) и определяется следующим образом: запишем числа \(x\) и \(y\) в двоичной системе счисления, дополнив при необходимости более короткое из них ведущими нулями до равной длины. Тогда \(x \oplus y\) это целое неотрицательное число, каждый разряд которого в двоичной системе счисления является исключающим ИЛИ соответствующих разрядов чисел \(x\) и \(y\). Например, \(5 \oplus 22 = 101_2 \oplus 10110_2 = 10011_2 = 19\).
Побитовое исключающее ИЛИ нескольких чисел можно посчитать, применяя последовательно операцию \(\oplus\) к предыдущему результату. Например, \(a \oplus b \oplus c \oplus d\) = \(((a \oplus b) \oplus c) \oplus d\). Можно показать, что результат не зависит от порядка вычисления.
В первой строке дано одно число \(n\) (\(1 \le n \le 100\,000\)) — количество вершин дерева.
В следующих \(n-1\) строках вводятся по 2 числа \(u\) и \(v\) — концы рёбер дерева.
В последней строке находятся \(n\) чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — числа в вершинах дерева.
В единственной строке выведите максимальное количество самостоятельных деревьев, на которое можно разбить данное дерево, или «-1», если такого разбиения не существует.
В первом тесте дерево выглядит так:
Если удалить рёбра, обозначенные крестиком, то мы получим 3 самостоятельных дерева. Можно показать, что на большее количество разбить нельзя.
6 1 2 1 3 2 4 2 5 3 6 2 1 1 0 1 3
3
3 1 2 2 3 1 1 1
-1