|Author:||M. Sporyshev||Time limit:||1 sec|
|Input file:||input.txt||Memory limit:||256 Mb|
Young programmer Vasya lives in a city where streets can be represented by a tree. Each vertex of a tree correspond to an intersection, each edge — to a street. So number of streets in the city is 1 less than a number of intersections. It is possible to get from from each intersection to every other one by streets.
There are two kinds of streets — residential and office ones.
City administration wants to create a looping road, represented by a cycle of streets. To minimize spending, only a single road of either kind must be built, creating a cycle. To satisfy zoning regulations, cycle must consist of at least 4 streets and number of residential streets in the cycle must be equal to the number of office streets.
Young programmer Vasya is preparing a presentation for city mayor and wants to add a slide with the total number of ways to add a street to the city road system, while satisfying all requirements. Your program must calculate that number.
Input file contains integer N — number of intersections in the city, followed by N − 1 triplets of integers u, v, c — numbers of intersections connected by street (u, v) and the kind of the street. c = 0 — residential street, c = 1 — office street.
Output file must contain a single integer — number of ways.
3 ≤ N ≤ 3000
0 ≤ u, v < N
|No.||Input file (
||Output file (|