Сумма XOR по путям дерева
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
2.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Сумма XOR по путям дерева
В Нарынской области n сёл соединены n-1 дорогами так, что от любого села можно доехать до любого другого. У каждой дороги есть число w. «Значение пути» между двумя сёлами — побитовое исключающее ИЛИ чисел на дорогах пути. Найдите сумму значений путей по всем неупорядоченным парам разных сёл.
Ввод. В первой строке n (2 ≤ n ≤ 10⁵). Далее n-1 строк: u, v, w (1 ≤ u, v ≤ n, 0 ≤ w < 2³⁰) — дорога между сёлами u и v.
Вывод. Сумма.
Пример 1
Ввод:
3
1 2 1
2 3 2
Вывод:
6
Комментарии