[CTSC2010] 珠宝商

Louis.PS 是一名精明的珠宝商，他出售的项链构造独特，很大程度上是因为他的制作方法与众不同。每次 Louis.PS 到达某个国家后，他会选择一条路径去遍历该国的城市。在到达一个城市后，他会使用在这个城市流行的材料制作一颗珠子，并按照城市被访问的顺序将珠子串联做成项链，为了使制作出来的项链不会因为城市之间的竞争而影响销量，路径中同一个城市不会重复出现（因为如果项链中 $A$ 城市的材料比 $B$ 城市的材料使用的多，则项链在 $B$ 城市的宣传可能会受到影响）。经过多年对消费者的调查，Louis.PS 已经掌握了判断一条项链吸引消费者程度的方法，具体来说，Louis.PS 经过调查得出了受消费者欢迎的项链的特征，并基于此制作了一个长项链（Louis.PS 称之为特征项链）。对于一条待售的项链，这条项链在特征项链里出现的次数越多，这条项链就越受消费者欢迎。 考虑到现实情况的复杂性，我们对条件做出适当的简化。对于每个国家，在某些城市间存在道路直接相连，对于两个不同的城市，有且仅有一条路径连接这两个城市（即国家是连通的，且不存在一个环）。对于每个城市，我们用一个小写字母来表示在这个城市流行的材料类型。这样，我们就可以用一个仅包含小写字母的字符串来表示一条项链，我们将特征项链所对应的字符串称作特征字符串，设为 $\mathit{EigenString}[1\ldots M]$，$M$ 为特征项链的长度。对于一条项链，假设其对应字符串为 $P[1\ldots L]$，$L$ 为这条项链的长度。如果存在一个正整数 $K$，使 $\mathit{EigenString}[K\ldots K+L-1]=P[1\ldots L]$，称这条项链在特征项链中出现了一次。满足上述条件的正整数 $K$ 的个数即为这条项链在特征项链的出现次数，记为 $\mathit{Popularity}(P)$。 Louis.PS 使用数学中的期望概念来评价一个国家是否适合珠宝的采集,对于一个包含 $N$ 个城市的国家，令 $\mathit{Str}_{u,v}$ 表示沿着从 $u$ 开始,至 $v$ 结束的路径所得到的项链的对应字符串。（$\mathit{Str}_{u,v}$ 与 $\mathit{Str}_{v,u}$ 表示的串一般不相同），则 $$ \mathit{Expectation}=\frac{\sum_{u,v}{\mathit{Popularity}(\mathit{Str}_{u,v})}}{N^2} $$ 对于如下的例子（图中实线表示两端点的国家有直接道路相连）： $N=3$，所流行的材料类型分别为 $\tt{a,a,b}$。  $$ \mathit{Expectation}=\frac{3+1+2+1+3+1+1+1+2}{9}=\frac53 $$ 对于一个国家，Louis.PS 想知道其 $\mathit{Expectation}$ 的值，但苦于计算期望的工作量太大。作为珠宝店的学徒，你当然不愿放过难得在老板面前展示自己的机会。

输入第一行包含两个整数 $N,M$，表示城市个数及特征项链长度。 接下来的 $N-1$ 行，每行两个整数 $x,y$，表示城市 $x$ 与城市 $y$ 有直接道路相连。城市由 $1\sim N$ 进行编号。 接下来的一行，包含一个长度为 $N$，仅包含小写字母的字符串，第 $i$ 位的字符表示在城市 $i$ 流行的原料类型。 最后一行，包含一个长度为 $M$，仅包含小写字母的字符串， 表示特征字符串。

输出仅包含一个整数，为 $N^2\times\mathit{Expectation}$。

3 5
1 2
1 3
aab
abaab

15

有 $20\%$ 的数据，满足 $M \leq 1000$； 有 $40\%$ 的数据，满足ܰ $N \leq 8000, M \leq 50000$； 对于 $100\%$ 的数据，$N,M \leq 50000$。