题目描述

给你一棵包含 $n$ 个节点的树。树上节点编号从 $1$ 到 $n$。

书上的每条边都有一个权值，每条边的权值不是 $0$ 就是 $1$。方便起见，我们接下来称权值为 $0$ 的边为 “$0$ 边”，称权值为 $1$ 的边为 “$1$ 边”。

我们称一对节点对 $(x, y)$（$x \neq y$）是一个 有效的 节点对，当且仅当：

从节点 $x$ 出发到节点 $y$ 的简单路径中，一开始是若干条（可能为 $0$ 条）连续的 $0$ 边，接着是若干条（可能为 $0$ 条）连续的 $1$ 边。

也就是说，存在从 $x$ 到 $y$ 的路径，且一旦你经过 $1$ 边了就不能再经过 $0$ 边，则 $(x, y)$ 就是一个有效的节点对。

输入格式

第一行，一个整数 $n(2 \le n \le 2 \cdot 10^5)$，表示树的大小。

接下来 $n-1$ 行，每行包含三个整数 $x_i, y_i, c_i$（$1 \le x_i, y_i \le n, 0 \le c_i \le 1, x_i \le y_i$），表示存在一条连接节点 $x_i$ 和节点 $y_i$ 的边，它的权值为 $c_i$。

数据保证这是一棵树。

输出格式

输出一个整数，表示有效的节点对数。

样例

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

34

说明/提示

样例 1 配图

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$
• 对于 $50\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$2 \le n \le 2 \cdot 10^5$