← 返回题目列表

Codeforces · 1156/D

D. 0-1-树

中文机器翻译题面 查看原题

给你一棵树(无向连通无环图),由 $$$n$$$ 个顶点和 $$$n - 1$$$ 条边组成。每条边上都写有一个数字,每个数字要么是$$$0$$$(我们称这些边为$$$0$$$-边),要么是$$$1$$$(这些是$$$1$$$-边)。

我们称一对有序顶点 $$$(x, y)$$$ ($$$x \ne y$$$) 有效,如果在遍历从 $$$x$$$ 到 $$$y$$$ 的简单路径时,我们在经过 $$$1$$$-边之后从未经过 $$$0$$$-边。您的任务是计算树中有效对的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200000$$$) — 树中的顶点数。

然后是 $$$n - 1$$$ 行,每行表示树的一条边。每条边由三个整数 $$$x_i$$$、$$$y_i$$$ 和 $$$c_i$$$ 表示 ($$$1 \le x_i, y_i \le n$$$, $$$0 \le c_i \le 1$$$, $$$x_i \ne y_i$$$) — 分别是这条边连接的顶点和上面写的数字。

保证给定的边形成一棵树。

输出

打印一个整数 — 有效顶点对的数量。

示例

输入 #1

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

输出 #1

34

注意

第一个例子对应的图片: