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

Задача . Yin and Yang

Задача

Фермер Джон планирует утренную прогулку по ферме. Ферма имеет структуру как дерево: имеется N амбаров (1 <= N <= 100,000), которые соединены N-1 дорожками по которым можно ойти о одного амбара в другой. ФД хочет выбрать путь, который начнется и закончится в различных амбарах, так чтобы не проходить ни по какой дорожке дважды. Поскольку путь может оказаться слишком длинным, он хочет определить "амбар отдыха", который лежит на пути и отличается от стартового и конечного амбаров.
Вдоль каждой дорожки гуляет стадо белых или стадо черных коров. Поэтому ФД хочет выбрать такой путь, чтобы он прошел одинаковое количество белых и черных стад в обоих случаях - и на пути от старта к "амбару отдыха", и на пути от "амбара отдыха" к финишу.
ФД интересуется сколько существует различных путей, обладающих свойствами, описанными выше. Два пути различаются, если они содержат различные множества дорожек. Путь должен считаться один раз, даже если может быть множество "амбаров отдыха" на этом пути. Вычислите это количество для ФД.
PROBLEM NAME: yinyang
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..N: Три целых числа a_i, b_i и t_i, представляющих два амбара, которые соединяет эта дорожка. t₀ равно 0 если вдоль дорожки пасутся белые коровы и 1, если черные.
Формат выходных данных
* Строка 1: Одно целое число, представляющее количество возможных путей ФД
Примечание
Никакой из путей длины 2 не имет подходящегоамбара для остановки. Поэтому должны рассматривать только пути длины 4. Единственный подходящий путь 3-1-2-5-7 с остановкой в 2.

Примеры

№	Входные данные	Выходные данные
1	7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1	1

time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет