eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Сума XOR

Сума XOR

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Задано дерево з n вершинами. Ребра дерева мають вагу лише 0 або 1. Знайдемо XOR суму між усіма парами вершин. Обчисліть суму усіх XOR сум.

Вхідні дані

Перший рядок містить кількість вершин у графі n~(2 \le n \le 10^5). Наступні n - 1 рядків описують ребра. Кожен рядок містить три цілих числа: номери вершин, що з'єднані ребром (вершини нумеруються числами від 1 до n), та вагу ребра (0 або 1).

Вихідні дані

Виведіть суму XOR сум між усіма парами вершин.

Приклад

Вхідні дані #1
5
1 2 1
2 3 1
2 4 0
4 5 1
Вихідні дані #1
6
Автор Михаил Медведев