在 Trie 上计数失败 - 题目

在计算机科学中，Trie（又称前缀树）是一种搜索树，即一种有序树数据结构，其键通常为字符串。

这里我们有一个包含 $n+1$ 个节点的 Trie，节点编号为 $0$ 到 $n$，根节点为 $0$ 号节点。Trie 中的所有边都从高度较低的节点指向高度较高的节点。每条边仅包含一个小写字母，且从同一个节点出发的任意两条边所包含的字符均不相同。

我们希望在 Trie 上为任意字符串 $T[1..k]$ 引入一种特殊的匹配方式。匹配从根节点开始，按顺序考虑所有字符 $T[1], T[2], \dots, T[k]$，并沿着从当前节点出发且包含当前考虑字符的边移动。如果匹配到达某个节点但无法沿着任何边移动，则：

最终，在考虑完 $T$ 中的所有字符后，匹配将停留在 Trie 上的某个节点，该节点即为匹配的终点。我们将终点的编号记为 $Dest(T)$，并将匹配过程中的失败总次数记为 $CFail(T)$。

现在给定一个长度为 $m$ 的小写字母字符串 $S[1..m]$，你需要回答 $q$ 个查询。查询定义为：

$$Query(l, r) = (CFail(S[l..r]), Dest(S[l..r]))$$

该查询询问的是 $S$ 的子串 $S[l..r]$ 在匹配过程中的失败总次数和匹配终点。

输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $1000$。

对于每个测试用例，第一行包含三个整数 $n, m$ 和 $q$，分别表示 Trie 中的节点数、给定字符串 $S$ 的长度以及查询总数，其中 $1 \le n, m, q \le 10^5$。

接下来的 $n$ 行描述了 Trie。其中第 $i$ 行包含一个整数 $f_i$（满足 $0 \le f_i < i$）和一个小写字母 $c_i$，分别描述了第 $i$ 号节点的父节点以及连接它们边的字符。

下一行包含一个长度为 $m$ 的小写字母字符串 $S$。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$，表示一个查询 $Query(l, r)$，其中 $1 \le l \le r \le m$。

保证所有测试用例中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和分别不超过 $10^6$。

对于每个测试用例，输出多行以回答所有查询。

对于每个查询，输出一行，包含两个整数，分别表示 $CFail(S[l..r])$ 和 $Dest(S[l..r])$。这两个数字之间应恰好有一个空格。

1
5 10 5
0 a
0 b
1 a
1 c
2 a
aaacbaacab
1 5
1 6
1 7
3 9
4 10

下图展示了样例测试用例中给出的 Trie。

所有查询的路径描述如下，其中每个 $\Rightarrow$ 表示一次失败：

$Path(1, 5) = Path(\text{“aaacb”}) = 0 \to 1 \to 3 \Rightarrow 0 \Rightarrow 0 \to 2$；
$Path(1, 6) = Path(\text{“aaacba”}) = 0 \to 1 \to 3 \Rightarrow 0 \Rightarrow 0 \to 2 \to 5$；
$Path(1, 7) = Path(\text{“aaacbaa”}) = 0 \to 1 \to 3 \Rightarrow 0 \Rightarrow 0 \to 2 \to 5 \Rightarrow 0$；
$Path(3, 9) = Path(\text{“acbaaca”}) = 0 \to 1 \to 4 \Rightarrow 0 \to 1 \to 3 \Rightarrow 0 \to 1$；
$Path(4, 10) = Path(\text{“cbaacab”}) = 0 \Rightarrow 0 \to 2 \to 5 \Rightarrow 0 \Rightarrow 0 \to 1 \Rightarrow 0$。

QOJ.ac