杰哥的树
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

一颗含有 n 个节点的树，树上的边权为小写拉丁字符集 中的字符。

询问这颗树有多少条不同的路径满足各个字符出现次数均为偶数次。

当且仅当两条路径上的节点个数和顺序完全相同时，称两条路径为相同路径。其他情况均为不同。

路径的长度至少为 。

输入描述:

第一行一个整数 n，表示 n 个树的节点数量。

接下来 n-1 行，每行输入两个整数 u，v，一个字符 ch。 u，v 分别表示两个节点的编号，ch表示链接 u，v 两点的边的边权。







输出描述:

一个整数，表示不同的路径数。
示例1

输入

复制 
7
1 2 a 
1 3 a 
2 4 a 
2 5 a 
3 6 a 
3 7 a

输出

复制 
11