题目描述

采药人的药田是一个树状结构，每条路径上都种植着同种药材。

采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。

采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

输入格式

第 $1$ 行包含一个整数 $N$。

接下来 $N-1$ 行，每行包含三个整数 $a_i,b_i,t_i$，表示这条路上药材的类型。

输出格式

输出符合采药人要求的路径数目。

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

1

数据规模与约定

对于 $100\%$ 的数据，$N\le 100,000$。