给定一颗 n$n$ 个结点的树,每条边上有一个小写字母。 令 str(x,y)$str(x,y)$ 表示树上 x$x$ 到 y$y$ 的简单路径上的字母连成的字符串。 定义一个字符串 T$T$ 是优秀的,当且仅当 T$T$ 能表示成 SS$SS$ 的形式,其中 S$S$ 是一个任意非空字符串。 求树上有多少个本质不同的优秀字符串。 输入格式 输入第一行一个正整数 n$n$,表示树的大小。 接下来 n−1$n-1$ 行,每行形如 x,y,c$x,y,c$ 表示有一条连接 (x,y)$(x,y)$ 的边,上面的小写字母是 c$c$。 输出格式 输出一个非负整数表示答案 样例一 input 5 1 2 a 2 3 a 3 4 b 4 5 b output 2 限制与约定 2≤n≤5×104$2\leq n\leq 5 \times 10^4$ 时间限制:5s$5\texttt{s}$ 空间限制:512MB$512\texttt{MB}$