题目描述

给一棵树，每条边上有一个字符，求有多少对 $(x,y)$（$x<y$），满足 $x$ 到 $y$ 路径上的边上的字符按顺序组成的字符串为回文串。

输入格式
第一行有一个整数：$n$；
接下来 $n-1$ 行，第 $i$ 行有三个整数 $x_i,y_i,z_i$，表示有一条连接 $x_i$ 和 $y_i$ 的边，边上的字符为 $z_i$。

输出格式
输出满足要求的点对数量。

样例
输入

4
1 2 0
1 3 0
1 4 1

输出

4

满足条件的有：$(1,2),(1,3),(1,4),(2,3)$。

见下发文件中的 ex_string2.in 与 ex_string2.out。
见下发文件中的 ex_string3.in 与 ex_string3.out。

数据范围与提示
子任务 1 [$5$ pts]：$n\leq 10$；
子任务 2 [$15$ pts]：$n\leq 5000$；
子任务 3 [$15$ pts]：对于所有的边，$x_i=i,y_i=i+1$；
子任务 4 [$25$ pts]：对于所有的边，$y_i=i+1,x_i$ 在 $[1,i]$ 之间随机。
子任务 5 [$40$ pts]：无特殊限制。

对于所有数据：$1\leq n\leq 50000,1\leq x_i,y_i\leq n,z_i\in\{0,1\}$。