Processing math: 100%

Problem H. Highway cycle

Author:M. Sporyshev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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 format

Input file contains integer N — number of intersections in the city, followed by N1 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 format

Output file must contain a single integer — number of ways.

Constraints

3N3000

0u,v<N

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
0 1 0
1 2 1
2 3 1
1
2
5
0 1 0
1 2 1
2 3 1
3 4 0
2

0.059s 0.008s 13