#28. 【CTSC2010】珠宝商

Type : Normal Time Limit : 12000 ms Memory Limit : 256 MiB
Input File : Standard Input Output File : Standard Outout Checker : Text Comparison

给出无根树 $T$,每个节点有一个字符。另给出字符串 $S$。求 $\sum_{u,v}\text{occur}(u,v)$。其中 $\text{occur}(u,v)$ 为 $T$ 中节点 $u$ 到节点 $v$ 的有向最短路径上的节点连成的字符串在 $S$ 中的出现次数。


输入格式

第一行包含两个整数 $N,M$,表示 $T$ 的节点个数及 $S$ 的长度。

接下来的 $N-1$ 行,每行两个整数 $x,y$,表示节点 $x$ 与节点 $y$ 有无向边相连。

节点由 $1$ ~ $N$ 进行编号。

接下来的一行,包含一个长度为 $N$,仅包含小写字母的字符串,第 $i$ 位的字符表示在节点 $i$ 的字符。

最后一行,包含一个长度为 $M$,仅包含小写字母的字符串,表示 $S$。

输出格式

一行一个整数为答案。


样例输入

3 5
1 2
1 3
aab
abaab

样例输出

15

限制与约定

20%的数据满足,$M\le 1000$。

40%的数据满足,$N\le 8000,M\le 50000$。

100%的数据满足,$N,M\le 50000$。

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

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

欢迎大家来虐神题!请不要卡评测姬>_<