TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4523
  • Problem
  • P4523「SDOI2016」模式字符串
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 2s,256m
    Description

    给出 \(n\) 个结点的树结构 \(T\),其中每一个结点上有一个字符,这里我们所说的字符只考虑大写字母 A 到 Z ,再给出长度为 \(m\) 的模式串 \(S\),其中每一位仍然是 A 到 Z 的大写字母。

    Alice 希望知道,有多少对结点 \(\langle u, v \rangle\) 满足 \(T\) 上从 \(u\)\(v\) 的最短路径形成的字符串可以由模式串 \(S\) 重复若干次得到?这里结点对 $\langle u,v \rangle$是有序的,也就是说 \(\langle u, v \rangle\)\(\langle v, u \rangle\) 需要被区分。所谓模式串的重复,是将若干个模式串 \(S\) 依次相接(不能重叠)。例如当 \(S =\)PLUS 的时候,重复两次会得到 PLUSPLUS,重复三次会得到 PLUSPLUSPLUS。同时要注意,重复必须是整数次的。例如当 \(S=\)XYXY 时,因为必须重复整数次,所以 XYXYXY 不能看作是 \(S\) 重复若干次得到的。

    Input Format

    每一个数据有多组测试,
    第一行输入一个整数 \(C\),表示总的测试个数。
    对于每一组测试来说:
    第一行输入两个整数,分别表示树 \(T\) 的结点个数 \(n\) 与模式长度 \(m\)。结点被依次编号为 $1$ 到 \(n\)
    之后一行,依次给出了 \(n\) 个大写字母(以一个长度为 \(n\) 的字符串的形式给出),依次对应树上每一个结点上的字符(第 \(i\) 个字符对应了第 \(i\) 个结点)。
    之后 \(n-1\) 行,每行有两个整数 \(u\)\(v\) 表示树上的一条无向边,之后一行给定一个长度为 \(m\) 的由大写字母组成的字符串,为模式串 \(S\)

    Output Format

    给出 \(C\) 行,对应 \(C\) 组测试。每一行输出一个整数,表示有多少对节点 \(\langle u,v \rangle\) 满足从 \(u\)\(v\) 的路径形成的字符串恰好是模式串的若干次重复。

    Sample Input

    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

    Sample Output

    5

    Hint

    对于所有的数据,$1 \leq C \leq 10, \ 3 \leq n \leq 1000000, 3 \leq M \leq 1000000$。