该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

文件输入输出提示

本题采用文件输入输出。提交代码时，请在 main 函数开头加入文件重定向，并从 palindrome.in 读入、输出到 palindrome.out。

freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);

题目描述

苗苗设计了一项校园回文路线挑战。校园中有 $n$ 个地点，由 $n-1$ 条道路连接成一棵树。每条道路上写有一个小写字母，字母范围为 a 到 t。

任意两个不同地点之间，都有唯一的一条简单路径。

对于两个地点 $u$ 和 $v$，把路径上所有道路的字母收集起来。如果这些字母重新排列后可以组成一个回文串，就称点对 $(u,v)$ 是一条“回文路线”。

请你统计有多少个不同的点对 $(u,v)$ 满足 $1\le u<v\le n$，并且 $(u,v)$ 是回文路线。

输入格式

从文件 palindrome.in 中读入数据。

第一行输入一个整数 $n$。

接下来 $n-1$ 行，每行输入两个整数 $u,v$ 和一个字符 $ch$，表示地点 $u$ 和地点 $v$ 之间有一条写着 $ch$ 的道路。

输出格式

输出到文件 palindrome.out 中。

输出一行一个整数，表示回文路线的数量。

输入输出样例 #1

输入 #1

5
1 2 a
2 3 b
2 4 a
4 5 b

输出 #1

7

说明/提示

满足条件的点对共有 7 个：

$(1,2)$、$(1,4)$、$(1,5)$、$(2,3)$、$(2,4)$、$(3,5)$、$(4,5)$。

例如 $(3,5)$ 的路径上字母为 b,a,b，可以重排为回文串 bab。

输入输出样例 #2

输入 #2

4
1 2 a
1 3 a
1 4 a

输出 #2

6

第二个样例中，任意两个地点之间路径上的字母都只包含 a，一定可以重排成回文串，因此 $4$ 个地点形成的 $6$ 个点对都满足要求。

数据范围与子任务

对于所有数据，满足：

• $2\le n\le 2\times 10^5$；
• 输入的道路保证构成一棵树；
• $ch$ 是从 a 到 t 的小写字母。

palindrome_大样例.zip