P4075 [SDOI2016] 模式字符串

给出 $n$ 个结点的树 $T$，其中每一个结点上有一个字符，这里我们所说的字符只考虑大写字母 A 到 Z，再给出长度为 $m$ 的模式串 $S$，其中每一位仍然是 A 到 Z 的大写字母。 Alice 希望知道，有多少对结点 $(u,v)$ 满足 $T$ 上从 $u$ 到 $v$ 的最短路径形成的字符串可以由模式串 $S$ 重复若干次得到l。 这里结点对 $(u,v)$ 是有序的，也就是说 $(u,v)$ 和 $(v,u)$ 需要被区分。 所谓模式串的重复，是将若干个模式串 $s$ 依次相接（不能重叠)。例如当 $S=$ `PLUS`的时候，重复两次会得到 `PLUSPLUS`，重复三次会得到 `PLUSPLUSPLUS`，同时要注意，重复必须是整数次的。例如当 $S= $ `XYXY` 时，因为必须重复整数次，所以 `XYXYXY` 不能看作是 $S$ 重复若干次得到的。

无

无

$1\leq C\leq 10$，$3\leq \sum N\leq 10^6$，$3\leq \sum M\leq 10^6$。