Preparing NOJ # 0-1-Tree

2000ms 262144K

## Description:

You are given a tree (an undirected connected acyclic graph) consisting of $n$ vertices and $n - 1$ edges. A number is written on each edge, each number is either $0$ (let's call such edges $0$-edges) or $1$ (those are $1$-edges).

Let's call an ordered pair of vertices $(x, y)$ ($x \ne y$) valid if, while traversing the simple path from $x$ to $y$, we never go through a $0$-edge after going through a $1$-edge. Your task is to calculate the number of valid pairs in the tree.

## Input:

The first line contains one integer $n$ ($2 \le n \le 200000$) — the number of vertices in the tree.

Then $n - 1$ lines follow, each denoting an edge of the tree. Each edge is represented by three integers $x_i$, $y_i$ and $c_i$ ($1 \le x_i, y_i \le n$, $0 \le c_i \le 1$, $x_i \ne y_i$) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.

## Output:

Print one integer — the number of valid pairs of vertices.

## Sample Input:

 7 2 1 1 3 2 0 4 2 1 5 2 0 6 7 1 7 2 1

## Sample Output:

 34

## Note:

The picture corresponding to the first example: Info Provider CodeForces

Code CF1156D

Tags

dfs and similardivide and conquerdpdsutrees

Submitted 38

Passed 9

AC Rate 23.68%

Date 07/21/2019 13:37:40

Related

Nothing Yet