题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

1

提示

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

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