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:

Sample Output:

Note:

The picture corresponding to the first example:

$\text{[math]}$

Informação

Provedor Codeforces

Código CF1156D