0-1-Tree

题意翻译

给定一棵 $n$ 个点的边权为 $0$ 或 $1$ 的树，一条合法的路径 $(x,y)$（$x\neq y$）满足，从 $x$ 走到 $y$，一旦经过边权为 $1$ 的边，就不能再经过边权为 $0$ 的边。求有多少路径满足条件？

题目描述

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.

输入输出样例

输入样例 #1

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

输出样例 #1

34

说明

The picture corresponding to the first example: