题目描述

给定一棵 $n$ 个点的树，每条边的长度有一个边权，现在定义 $dis(i,j)$ 代表第 $i$ 个点到第 $j$ 个点的距离模 $2$ 之后的结果。问有多少对 $(i,j,k)$ 满足， $dis(i,j)=dis(i,k)=dis(j,k)$。 注意：这里的 $i,j,k$ 可以相等。

输入格式

第一行一个整数 $n$ 代表点的数量。 接下来 $n-1$ 行每行三个整数 $u,v,w$ 代表有一条在 $u,v$ 之间长度为 $w$ 的边.

输出格式

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

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

3
1 2 3
1 3 4

输出 #2

9

说明/提示

样例解释：

在第一组样例中，只有 $(1,1,1)$ 满足条件，因此答案为 $1$ 。

在第二组样例中，$(1,1,1)，(2,2,2)，(3,3,3)，(1,3,1)，(1,1,3)，(3,1,1)，(3,3,1), (3,1,3)，(1,3,3)$ 均符合条件，并可以验证不存在其它点对满足条件，因此答案为 $9$。

数据规模与约定：

对于 $30$%的数据，$1≤n≤20$。

对于 $60$%的数据，$1≤n≤100$。

对于 $100$%的数据，$1≤n≤1000，0≤w≤233$。