Сумма 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

Комментарии

Еще нет ни одного комментария.