Description

You are given a tree $T$ with $n$ nodes, where each node has a character. The characters are uppercase letters A to Z. You are also given a pattern string $S$ of length $m$, where each character is also an uppercase letter A to Z.

Alice wants to know how many ordered pairs of nodes $(u,v)$ satisfy that the string formed by the shortest path from $u$ to $v$ in $T$ can be obtained by repeating the pattern string $S$ some number of times.

Here the pair $(u,v)$ is ordered, meaning $(u,v)$ and $(v,u)$ are considered different.

Repeating a pattern string means concatenating several copies of the pattern string $s$ one after another (without overlap). For example, when $S=$ PLUS, repeating it twice yields PLUSPLUS, repeating it three times yields PLUSPLUSPLUS. Note that the number of repetitions must be an integer. For example, when $S=$ XYXY, since repetitions must be an integer number, XYXYXY cannot be regarded as obtained by repeating $S$ some number of times.

Input Format

There are multiple test cases.

The first line contains an integer $C$, the total number of test cases.

For each test case:

• The first line contains two integers, the number of nodes $n$ of the tree $T$ and the pattern length $m$. Nodes are numbered from $1$ to $n$.
• The next line gives $n$ uppercase letters (as a string of length $n$), where the $i$-th character corresponds to the $i$-th node on the tree.
• The next $n-1$ lines each contain two integers $u$ and $v$, indicating an undirected edge of the tree.
• The last line gives the pattern string $S$, which is a string of length $m$ consisting of uppercase letters.

Output Format

Output $C$ lines, one for each test case.

Each line should contain one integer, the number of ordered pairs $(u,v)$ such that the string formed by the path from $u$ to $v$ is exactly an integer number of repetitions of the pattern string $S$.

1
11 4
IODSSDSOIOI
1 2
2 3
3 4
1 5
5 6
6 7
3 8
8 9
6 10
10 11
SDOI

5

Hint

$1 \leq C \leq 10$, $3 \leq \sum n \leq 10^6$, $3 \leq \sum m \leq 10^6$.

Translated by ChatGPT 5