UOJ Logo Universal Online Judge

UOJ

#281. sone3

统计

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

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

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

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

输入格式

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

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

输出格式

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

样例一

input

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

output

2

限制与约定

$2\leq n\leq 5 \times 10^4$

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$