题目描述

农夫约翰正在计划他早上在农场散步。农场的结构像一棵树：它有 $\red{N }$个谷仓 $\red{(1 <= N <= 100,000)，}$它们由 $\red{N-1 }$条边连接，这样他就可以从任何其他谷仓到达任何谷仓。$\red{Farmer John }$想要选择一条在两个不同的谷仓开始和结束的路径，这样他就不会两次遍历任何边缘。他担心他的路径可能有点长，所以他也想选择另一个位于这条路径上的"休息站"谷仓（与起点或终点不同）。

沿着每个边缘是一群奶牛，无论是夏科莱（白毛）还是安格斯（黑毛）品种。作为一个聪明人，农夫约翰想要平衡影响他行走的阴阳力量。为此，他希望选择一条路径，使得他将经过同等数量的夏科莱牛群和安格斯 牛群——无论是在从起点到休息站的路上，还是从休息站到终点的路上.

$\red{Farmer John }$很好奇他可以选择多少种如上所述"平衡"的不同路径。只有当它们由不同的边集组成时，两条路径才不同；即使沿路径有多个有效的"休息站"位置使其平衡，一条路径也应该只计算一次。

请帮助确定 $\red{Farmer John }$可以选择的路径数量！

给出一棵$\red{n}$个点的树，每条边为黑色或白色。问满足以下条件的路径条数：路径上存在一个不是端点的点，使得两端点到该点的路径上两种颜色的边数都相等。

输入格式

第 $\red{1 }$行：整数 $\red{N}$。

第 $\red{2..N }$行：三个整数 $\red{a_i}$、$\red{b_i }$和 $\red{t_i，}$代表边 $\red{i }$连接的两个谷仓。如果沿着该边缘的畜群是 $\red{Charcolais，}$则 $\red{t_i }$为 $\red{0，}$如果畜群为 $\red{Angus，}$则为 $\red{1}$。

输出格式

第 $\red{1 }$行：一个整数，代表 $\red{Farmer John }$可以选择的可能路径的数量。

样例

输入样例

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

输出样例

1

提示

有$\red{7}$个谷仓和$\red{6}$个边缘。从 $\red{1 }$到 $\red{2}$、$\red{2 }$到 $\red{4 }$和 $\red{2 }$到 $\red{5 }$的边沿有夏可莱牛群。

长度为 $\red{2 }$的路径上不能有合适的停靠点，所以我们只能考虑长度为 $\red{4 }$的路径。唯一有合适停靠点的路径是 $\red{3-1-2-5-7，}$停靠点位于 $\red{2 .}$