UOJ Logo Universal Online Judge

UOJ

#281. sone3

附件下载 统计

给定一颗 n 个结点的树,每条边上有一个小写字母。

str(x,y) 表示树上 xy 的简单路径上的字母连成的字符串。

定义一个字符串 T 是优秀的,当且仅当 T 能表示成 SS 的形式,其中 S 是一个任意非空字符串。

求树上有多少个本质不同的优秀字符串。

输入格式

输入第一行一个正整数 n,表示树的大小。

接下来 n1 行,每行形如 x,y,c 表示有一条连接 (x,y) 的边,上面的小写字母是 c

输出格式

输出一个非负整数表示答案

样例一

input

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

output

2

限制与约定

2n5×104

时间限制:5s

空间限制:512MB