Задачі
Сума XOR
Сума XOR
Задано дерево з 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