P4075 [SDOI2016] Pattern String

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.

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 $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 \leq C \leq 10$, $3 \leq \sum n \leq 10^6$, $3 \leq \sum m \leq 10^6$. Translated by ChatGPT 5