CF1045J Moonwalk challenge

自从 BubbleCup XI 任务的宇航员们完成了他们在月球上的任务后，作为著名歌手的粉丝，他们决定在返回地球前玩一会儿，于是创造了一个名为“月球漫步挑战”的游戏。 宇航员们被分成若干小队，每队会获得一张月球陨石坑的地图，以及一些可以安全“月球漫步”的双向直达路径。每条直达路径都有一种颜色，并且任意两个陨石坑之间有且仅有一条唯一的路径。游戏的目标是找到一对陨石坑，使得给定的颜色数组在这两点之间的路径上作为连续子数组出现的次数最多（重叠出现也要计数）。 为了帮助你喜欢的队伍获胜，你需要编写一个程序，给定地图后，回答如下类型的查询：对于两个陨石坑和一个颜色数组，回答该颜色数组作为连续子数组在这两点之间的路径上出现了多少次（重叠出现也要计数）。 颜色用小写英文字母表示。

第一行，一个整数 $N$（$2 \leq N \leq 10^5$），表示月球上的陨石坑数量。陨石坑编号为 $1$ 到 $N$。 接下来的 $N-1$ 行，每行包含三个值 $u, v, L$（$1 \leq u, v \leq N, L \in \{a, ..., z\}$），表示在陨石坑 $u$ 和 $v$ 之间有一条颜色为 $L$ 的双向直达路径。 下一行包含一个整数 $Q$（$1 \leq Q \leq 10^5$），表示查询的数量。 接下来的 $Q$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq N$）和一个字符串 $S$（$|S| \leq 100$），其中 $u$ 和 $v$ 是你需要查询的两个陨石坑，$S$ 是表示颜色数组的字符串。你需要回答 $S$ 作为连续子数组在 $u$ 到 $v$ 的路径上出现了多少次。

对于每个查询，输出一个整数，表示 $S$ 在 $u$ 到 $v$ 的路径上作为连续子数组出现的次数。

由 ChatGPT 4.1 翻译