Задача E. Highway cycle ≡

Условие

Улицы города, в котором живет юный программист Вася, могут быть представлены в виде дерева. Каждая вершина дерева соответствует перекрестку, а каждое ребро — улице. Таким образом, улиц в городе на 1 меньше, чем перекрестков. Из каждого перекрестка по улицам можно добраться до любого другого.

Улицы в городе бывают двух типов — жилые или офисные.

Администрация города хочет сделать в городе кольцевую автодорогу, которая должна представлять из себя цикл из улиц. Чтобы потратить поменьше денег, необходимо построить ровно одну новую улицу любого из двух типов, чтобы получить цикл. Чтобы выполнить требования генерального плана города, необходимо, чтобы в полученном цикле было не менее 4 улиц и количество жилых улиц совпадало с количеством офисных.

Юный программист Вася готовит презентацию для мэра города и хочет добавить слайд, на котором указано количество способов добавить улицу к системе дорог в городе, удовлетворяющую всем требованиям. Ваша программа должна рассчитывать это число.

Формат входного файла

Входной файл содержит целое число N — количество перекрестков в городе, за которым следует N − 1 троек целых чисел u, v, c — номера перекрестков, соединенных улицей (u, v) и тип улицы. c = 0 — жилая улица, c = 1 — офисная улица.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов.

Ограничения

3 ≤ N ≤ 3000

0 ≤ u, v < N

Примеры тестов

4
0 1 0
1 2 1
2 3 1

1

5
0 1 0
1 2 1
2 3 1
3 4 0

2