Задано дерево (неориентированный связный ацикличный граф), состоящее из \(n\) вершин и \(n - 1\) ребра. На каждом ребре записано число, каждое из чисел — это либо \(0\) (назовем такие ребра \(0\)-ребрами), либо \(1\) (назовем их \(1\)-ребрами).
Назовем упорядоченную пару вершин \((x, y)\) (\(x \ne y\)) корректной, если при проходе по простому пути от \(x\) до \(y\) мы никогда не пройдем по \(0\)-ребру после прохода по \(1\)-ребру. Ваша задача — посчитать количество корректных пар в дереве.
Первая строка входных данных содержит одно целое число \(n\) (\(2 \le n \le 200000\)) — количество вершин в дереве.
Затем следует \(n - 1\) строка, каждая из которых описывает ребро дерева. Каждое ребро представлено в виде трех целых чисел \(x_i\), \(y_i\) и \(c_i\) (\(1 \le x_i, y_i \le n\), \(0 \le c_i \le 1\), \(x_i \ne y_i\)) — вершины, соединенные этим ребром, и число, записанное на нем, соответственно.
Гарантируется, что заданный набор ребер формирует дерево.
Выведите одно целое число — количество корректных пар вершин.
Картинка, соответствующая первому тестовому примеру:
7 2 1 1 3 2 0 4 2 1 5 2 0 6 7 1 7 2 1
34
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач