CF1156D 0-1-Tree

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.

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.

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

The picture corresponding to the first example: