P17476 [ICPC 2018 Jiaozuo R] Counting Failures on a Trie
题目描述
在计算机科学中，trie，又称前缀树，是一种搜索树，一种有序的树形数据结构，其键通常为字符串。
这里我们有一棵包含 $(n + 1)$ 个节点的 trie，节点编号为 $0$ 到 $n$，其根为编号 $0$ 的节点。trie 中的所有边均从高度较低的节点指向高度较高的节点。每条边仅包含一个小写字母，且从同一节点出发的任意两条边所具有的字符互不相同。
我们希望在 trie 上为任意字符串 $T[1..k]$ 引入一种特殊的匹配过程。
匹配将从根开始，按顺序依次考虑所有字符 $T[1], T[2], \cdots, T[k]$，并沿着某条从当前节点出发且包含当前所考虑字符的边移动。如果匹配到达某个节点后无法沿任何边继续移动，则：
* 它将在当前字符处记录一次失败，跳过该字符并移回根节点；
* 随后它将在下一次匹配步中考虑下一个字符，因为**失败的字符应当被跳过**。
最终，在考虑完 $T$ 中的所有字符后，匹配将停留在 trie 的某个节点上，该节点指示了此次匹配的目的地。我们将目的地的编号记作 $Dest(T)$，并将匹配过程中失败的总次数记作 $CFail(T)$。
现在，我们给你一个长度为 $m$ 的全小写字母字符串 $S[1..m]$，你需要回答 $q$ 个查询。一个查询定义为
$$\displaystyle Query(l, r) = (CFail(S[l..r]), Dest(S[l..r])),$$
即询问 $S$ 的子串 $S[l..r]$ 所对应的匹配失败总次数及目的地。
输入格式
输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多为 $1000$。
对于每组测试数据，第一行包含三个整数 $n$、$m$ 和 $q$，分别表示 trie 的节点数、给定字符串 $S$ 的长度以及查询的总数，满足 $1 \leq n, m, q \leq 10^5$。
接下来的 $n$ 行描述 trie。其中第 $i$ 行包含一个整数 $f_i$（满足 $0 \leq f_i < i$）和一个小写字母 $c_i$，分别表示第 $i$ 个节点的父节点以及连接它们的边上的字符。
再接下来一行包含一个全小写字母的字符串，表示给定的长度为 $m$ 的字符串 $S$。
最后 $q$ 行中的每一行包含两个整数 $l$ 和 $r$，表示一个查询 $Query(l, r)$，满足 $1 \leq l \leq r \leq m$。
我们保证所有测试数据中 $n$ 的总和、$m$ 的总和以及 $q$ 的总和均分别不超过 $10^6$。
输出格式
对于每组测试数据，输出若干行以回答所有查询。
对于每个查询，输出一行包含两个整数，分别表示 $CFail(S[l..r])$ 和 $Dest(S[l..r])$。你应在两个数字之间恰好输出一个空格。
说明/提示
下图展示了样例测试数据中给出的 trie。
:::align{center}
:::
所有查询的路径描述如下，其中每个 $\Longrightarrow$ 表示一次失败。
* $Path(1, 5) = Path(\text{``aaacb"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2;$
* $Path(1, 6) = Path(\text{``aaacba"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5;$
* $Path(1, 7) = Path(\text{``aaacbaa"}) = 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5 \Longrightarrow 0;$
* $Path(3, 9) = Path(\text{``acbaaca"}) = 0 \longrightarrow 1 \longrightarrow 4 \Longrightarrow 0 \longrightarrow 1 \longrightarrow 3 \Longrightarrow 0 \longrightarrow 1;$
* $Path(4, 10) = Path(\text{``cbaacab"}) = 0 \Longrightarrow 0 \longrightarrow 2 \longrightarrow 5 \Longrightarrow 0 \Longrightarrow 0 \longrightarrow 1 \Longrightarrow 0.$
翻译由 DeepSeek V4 Pro 完成