给出无根树 $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}$
欢迎大家来虐神题！请不要卡评测姬>_<
