Matcom Online Grader

A new family of trees has been found. These peculiar trees have exactly one fruit in each leaf and in each bifurcation, similar to a tree data structure. The weirdest characteristic of these plants is that they are able to produce up to 62 fruits of different types (represented with an English lowercase character, uppercase character or numeric digit). In order to classify them it is needed a function that, given a tree (with all its fruits) and a pattern (a sequence of fruits), counts how many simple paths in the tree are equal to the pattern. A simple path is defined as a sequence of nodes where two adjacent nodes in the sequence are adjacent in the tree and it does not contain repeated nodes. We say a simple path is equal to a pattern if when we replace the number of the node in the path (the sequence) by the fruit it contains, we obtain a sequence equal to the pattern.

The first line contains two integers $N$ and $L$ ($1 \le N, L \le 10^6$) indicating the number of nodes and the length of the pattern respectively. The second line has a string $S$ ($|S| = N$) where $S_i$ indicates the fruits contained in the node $i$. The third line contains the pattern $P$ ($|P| = L$) to find. Then next $N-1$ lines contains the structure of the tree with each line having two integers $a$ and $b$ $(0 \le a, b < N)$ indicating that these two nodes are adjacent.