2635 - 小K的疑惑

通过次数

6

提交次数

10

时间限制 : 1 秒
内存限制 : 512 MB

众所周知,小K是一只连NOIP2018初赛都没有过的蒟蒻,所以小K很擅长dfs序+分块树,但是本题与dfs序+分块树无关。 小K现在心态爆炸了,因为小K被一道简单的数据结构题给卡住了,希望请你来解决它,但是小K又不想太麻烦你,于是将题面进行了简化: Bob有N个点的树,每条边的长度有一个边权,现在定义dis(i,j)代表第i个点到第j个点的距离模2之后的结果。问有多少(i,j,k)满足dis(i,j)=dis(j,k)=dis(i,k).

输入

第一行一个整数N代表点的数量
接下来N-1行,每行三个数s,e,d代表有一条在s,e之间长度为d的边.

输出

一行一个整数代表有多少对(i,j,k)满足条件

样例

输入

3
1 2 3
1 3 4

输出

9

输入

4
2 1 227
3 1 40
4 3 197

输出

16

提示

对于100%的数据,1 ≤ N ≤ 10000,0 ≤ d ≤ 233。