解题思路

给定一棵以 1 为根的树，每个点携带一个大写字母。对每次询问 $(u,v)$ ，取树上从 $u$ 到 $v$ 的简单路径，依次读出字母，判断这个序列是否包含子序列 "BUG"；若不包含则输出 YES，否则输出 NO。

判断序列是否包含 "BUG" 可用一个 4 态自动机线性扫描完成：

题目内容

小美有一个结点总数为 $n$ 且根节点编号为 $1$ 的有根树。

第 $i$ 个结点的编号为 $i$ ,所携带的字母为 $a_i$ 。

小美是一名程序员,她认为一对 $(u,v)$ 是好对,当且仅当从节点 $u$ 到节点 $v$ 的简单路径上依次拼接得到字符串 $S$ 的子序列中不存在" $BUG$ "。