#P4598. [Sdoi2016]模式字符串

    ID: 1838 传统题 3000ms 128MiB 尝试: 422 已通过: 166 难度: 8 上传者: 标签>难度分类提高+/省选-树算法点分治字符串双哈希随机化与近似随机哈希模拟与实现技巧稀疏状态重置CF2400

[Sdoi2016]模式字符串

[SDOI2016] 模式字符串

题目描述

给定一棵 nn 个节点的树,每个节点标有一个大写英文字母。再给定一个由大写英文字母组成、长度为 mm 的模式串 SS。

对有序点对 (u,v)(u,v),沿从 uu 到 vv 的唯一路径依次读出字母,包含两个端点。当 u=vu=v 时只读该节点的一个字母。求有多少有序点对读出的字符串由一个或多个完整的 SS 依次拼接而成。(u,v)(u,v) 与 (v,u)(v,u) 在 u≠vu\ne v 时分别计数。

例如,若 SS 为 “PLUS”,则 “PLUSPLUS” 满足要求。若 SS 为 “XYXY”,则 “XYXYXY” 不满足要求。

输入格式

第一行一个整数 CC,表示测试组数。每组测试依次给出:

  1. 两个整数 n,mn,m,分别是节点数和模式串长度。节点编号为 11 到 nn。
  2. 一个长度为 nn 的大写字母串,第 ii 个字母是节点 ii 的标记。
  3. n−1n-1 行,每行两个整数 u,vu,v,表示一条无向边。
  4. 一个长度为 mm 的大写字母串 SS。

输出格式

输出 CC 行,每组输出满足条件的有序点对数。

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

数据范围

1≤C≤101\le C\le10。每组数据满足 1≤n≤1051\le n\le10^5、1≤m≤201\le m\le20。

原赛第一子任务占 2020 分,另有 n≤3000n\le3000 的限制。第二子任务占 8080 分,无额外限制。