Author: | M. Sporyshev | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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 (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|