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

CodeForces

Provider CodeForces

Origin Educational Codeforces Round 64 (Rated for Div. 2)

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