给你一棵树(无向连通无环图),由 $$$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
注意
第一个例子对应的图片: