P4218 [CTSC2010] Jeweler

Louis.PS is a shrewd jeweler whose necklaces have a unique construction, largely because his production method is different. Each time Louis.PS arrives in a country, he chooses a path to traverse the cities of that country. Upon arriving at a city, he makes a bead using the material popular in that city, and strings the beads together in the order the cities are visited to make a necklace. To prevent competition between cities from affecting sales, the path never visits the same city twice (because if the material from city $A$ is used more than that from city $B$ in the necklace, promotion in city $B$ may be affected). After years of consumer research, Louis.PS has learned how to judge how attractive a necklace is to consumers. Specifically, he has identified the features of popular necklaces and, based on this, has created a long necklace (which he calls the feature necklace). For a necklace for sale, the more times it appears in the feature necklace, the more popular it is. To simplify the complex reality, we make the following assumptions. In each country, some cities are directly connected by roads; for any two distinct cities, there is exactly one path connecting them (i.e., the country is connected and has no cycle). For each city, we use a lowercase letter to denote the material type popular in that city. Thus, we can represent a necklace by a string containing only lowercase letters. We call the string corresponding to the feature necklace the feature string, denoted as $\mathit{EigenString}[1\ldots M]$, where $M$ is the length of the feature necklace. For a necklace, suppose its corresponding string is $P[1\ldots L]$, where $L$ is the length of this necklace. If there exists a positive integer $K$ such that $\mathit{EigenString}[K\ldots K+L-1]=P[1\ldots L]$, we say this necklace appears once in the feature necklace. The number of such positive integers $K$ is the occurrence count of this necklace in the feature necklace, denoted as $\mathit{Popularity}(P)$. Louis.PS uses the mathematical concept of expectation to evaluate whether a country is suitable for material collection. For a country with $N$ cities, let $\mathit{Str}_{u,v}$ denote the string corresponding to the necklace obtained along the path starting at $u$ and ending at $v$ (in general, $\mathit{Str}_{u,v}$ and $\mathit{Str}_{v,u}$ are different). Then $$ \mathit{Expectation}=\frac{\sum_{u,v}{\mathit{Popularity}(\mathit{Str}_{u,v})}}{N^2} $$ For the following example (solid lines in the figure indicate that the endpoints are directly connected by a road): $N=3$, and the popular material types are $\tt{a,a,b}$.  $$ \mathit{Expectation}=\frac{3+1+2+1+3+1+1+1+2}{9}=\frac53 $$ For a given country, Louis.PS wants to know the value of $\mathit{Expectation}$, but the computation workload is large. As the apprentice, you certainly would not miss the chance to impress your boss.

The first line contains two integers $N, M$, the number of cities and the length of the feature necklace. The next $N-1$ lines each contain two integers $x, y$, indicating that city $x$ and city $y$ are directly connected by a road. Cities are numbered from 1 to $N$. The next line contains a string of length $N$ consisting only of lowercase letters. The $i$-th character indicates the material type popular in city $i$. The last line contains a string of length $M$ consisting only of lowercase letters, denoting the feature string.

Output a single integer, which is $N^2 \times \mathit{Expectation}$.

- 20% of the testdata satisfy $M \leq 1000$. - 40% of the testdata satisfy $N \leq 8000, M \leq 50000$. - For 100% of the testdata, $N, M \leq 50000$. Translated by ChatGPT 5