英文名称： hepta

题目描述

给定一个 $n$ 个节点的树，树的每条边是黑色或者白色，使用 $0$ 和 $1$ 来表示。

求有多少点对 $(x, y)$，满足 $x < y$，且从 $x$ 到 $y$ 的唯一简单路径上的颜色拼接在一起得到的 $01$ 串回文。

输入格式

第一行一个正整数 $n$，表示树的大小。

随后 $n - 1$ 行，每行两个正整数和一个非负整数 $x, y, z$，表示 $x, y$ 之间有一条颜色为 $z$ 的边。

保证边组成一棵树。

输出格式

一个非负整数，表示答案。

输入输出样例

输入样例 1

4
1 2 0
1 3 0
1 4 1

输出样例 1

4

输入样例 2

10
7 2 1
1 4 1
1 5 0
3 6 0
3 7 0
8 3 1
9 8 0
1 9 0
1 10 0

输出样例 2

20

样例 3 见文件。

大样例

数据范围

共 $20$ 个测试点。

测试点 $1\sim 4$，满足 $n\le 5000$。

测试点 $5\sim 7$，满足输入为一条链，且节点 $1$ 的度数为 $1$。

测试点 $8\sim 12$，树随机生成。

测试点 $13\sim 20$，无特殊限制。

对于所有数据满足 $1\le n\le 5\times 10^4$。

提示

请避免使用 $64$ 位自然溢出的哈希，建议使用对质数取模的双哈希。