LuoTianyi дала вам дерево со значениями в вершинах, корнем этого дерева является вершина \(1\).
За одну операцию вы можете изменить значение в любой вершине на любое неотрицательное целое число.
Вам нужно найти минимальное количество операций, которые нужно сделать, чтобы побитовое исключающее ИЛИ на любом пути от корня до листа\(^{\dagger}\) было равно нулю.
\(^{\dagger}\)Листом в корневом дереве называется вершина, которая имеет ровно одного соседа, и при этом не является корнем.
Примечание
Дерево из первого примера:
Если мы поменяем значение в вершине \(2\) на \(3\), значение в вершине \(5\) на \(4\), значение в вершине \(6\) на \(6\), то дерево станет подходящим.
Побитовое исключающее ИЛИ от корня до листа \(2\) будет равно \(3 \oplus 3=0\).
Побитовое исключающее ИЛИ от корня до листа \(5\) будет равно \(4 \oplus 7 \oplus 3=0\).
Побитовое исключающее ИЛИ от корня до листа \(6\) будет равно \(6 \oplus 5 \oplus 3=0\).
Дерево из второго примера:
Если мы поменяем значение в вершине \(2\) на \(4\), значение в вершине \(3\) на \(27\), значение в вершине \(6\) на \(20\), то дерево станет подходящим.
Побитовое исключающее ИЛИ от корня до листа \(6\) будет равно \(20 \oplus 19 \oplus 7=0\).
Побитовое исключающее ИЛИ от корня до листа \(8\) будет равно \(11 \oplus 27 \oplus 4 \oplus 19 \oplus 7=0\).
Побитовое исключающее ИЛИ от корня до листа \(4\) будет равно \(16 \oplus 4 \oplus 19 \oplus 7=0\).
Побитовое исключающее ИЛИ от корня до листа \(7\) будет равно \(16 \oplus 4 \oplus 19 \oplus 7=0\).
В третьем примере единственным листом является вершина \(4\), и побитовое исключающее ИЛИ на пути до неё равно \(1 \oplus 2 \oplus 1 \oplus 2 = 0\), поэтому нам не нужно изменять значения.
В четвёртом примере мы можем изменить значение в вершине \(1\) на \(5\), а значение в вершине \(4\) на \(0\).
Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.