Олимпиадный тренинг

Задача . D. 0-1-Дерево

Задача

Темы: Деревья дп поиск в глубину и подобное разделяй и властвуй *2200 снм

Задано дерево (неориентированный связный ацикличный граф), состоящее из $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$) — вершины, соединенные этим ребром, и число, записанное на нем, соответственно.

Гарантируется, что заданный набор ребер формирует дерево.

Выходные данные

Выведите одно целое число — количество корректных пар вершин.

Примечание

Картинка, соответствующая первому тестовому примеру:

$\text{[math]}$