n вершин с номерами от 0 до n - 1; рёбра заданы списком edges, где edges[i] = [a, b] соединяет вершины a и b. В вершине i записано число values[i].
Удалите из дерева ровно два разных ребра — оно распадётся на три связные части. Для каждой части посчитайте побитовый XOR чисел во всех её вершинах. *Разброс* разреза — это разница между наибольшим и наименьшим из трёх полученных XOR.
Верните наименьший возможный разброс.values=[6, 2, 3, 7, 4], edges=[[0, 1], [1, 2], [0, 3], [3, 4]] → 1
Перерезаем рёбра 1–2 и 3–4. Получаются части {2} с XOR 3, {4} с XOR 4 и {0, 1, 3} с XOR 6 ^ 2 ^ 7 = 3. Разброс 4 − 3 = 1, и меньше получить нельзя.
values=[9, 9, 5, 5], edges=[[0, 1], [1, 2], [2, 3]] → 5
Если перерезать 1–2 и 2–3, получатся {0, 1} с XOR 0 и {2}, {3} с XOR 5 у каждой — разброс 5. Другие пары рёбер дают больше: например, 0–1 и 2–3 дают XOR 9, 12 и 5, то есть разброс 7.
values=[1, 2, 3], edges=[[0, 1], [0, 2]] → 2
values=[6, 2, 3, 7, 4], edges=[[0, 1], [1, 2], [0, 3], [3, 4]]
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 57 тестов на сервере, включая скрытые.