AT_ijpc2015_j Верный

IOI2015 举办地阿拉木图，曾经被称为 Верный（维尔尼）。在俄语中，这个名字有「忠诚的」或「可信赖的」的意思。受此启发，joisino 决定测验一下她的下属对她的忠诚度。 为此，她准备了两棵树，分别命名为树 X 和树 Y。每棵树的顶点编号从 0 到 $(树的顶点数 - 1)$，且每个顶点上都有一个从 'a' 到 'j' 的小写字母。 接下来将执行 $Q$ 次操作： 1. 在树 X 的某路径上，交换从 $A$ 到 $B$ 上（包括 $A$ 和 $B$）的两个指定字母。例如，将 $'a'$ 和 $'b'$ 交换，会导致路径上的所有 $'a'$ 变成 $'b'$，$'b'$ 变成 $'a'$。 2. 在树 Y 的某路径上，交换从 $A$ 到 $B$ 上（包括 $A$ 和 $B$）的两个指定字母。同样地，将 $'a'$ 和 $'b'$ 交换，会导致路径上的所有 $'a'$ 变成 $'b'$，$'b'$ 变成 $'a'$。 3. 比较树 X 上从 $A$ 到 $B$ 的路径（包括 $A$ 和 $B$）上的字母组成的字符串，和树 Y 上从 $C$ 到 $D$ 的路径（包括 $C$ 和 $D$）的字母组成的字符串，看它们是否相同。 4. 回退到进行了 $a$ 次操作后的状态。这里 $0 \le a \le （当前已处理的操作次数）$。

输入数据包括： 1. 树 X 的数据 2. 树 Y 的数据 3. 查询次数 $Q$ 4. 接下来的 $Q$ 个查询 每棵树的数据结构如下： - 首先，给出一个整数 $N$，表示树的顶点数。 - 接着是一串长度为 $N$ 的字符串 $s$。其中第 $i+1$ 个字符表示顶点 $i$ 上的字母。 - 随后的 $N-1$ 行，每行由两个整数 $a_i$ 和 $b_i$ 组成，表示在顶点 $a_i$ 和 $b_i$ 之间有一条边。 每个查询由以下格式组成： - 当查询类型 $t = 0$ 时，之后有整数 $a, b$ 和字符 $c, d$。表示在树 X 的顶点 $a$ 到顶点 $b$ 之间，将所有 $c$ 替换为 $d$，所有 $d$ 替换为 $c$。 - 当查询类型 $t = 1$ 时，结构与 $t = 0$ 相同，只不过是对树 Y 进行上述操作。 - 当查询类型 $t = 2$ 时，之后有四个整数 $a, b, c, d$。表示判断树 X 上从 $a$ 到 $b$ 的路径上的字母组成的字符串，与树 Y 上从 $c$ 到 $d$ 的路径组成的字符串是否相同。 - 当查询类型 $t = 3$ 时，有一个整数 $a$。表示将两棵树的状态恢复到执行了 $a$ 次查询后的状态。

对于每个类型为 $t = 2$ 的查询，如果两串字符串相同，则输出 `YES`；否则输出 `NO`。注意最后一行输出之后要换行。

- $1 \le Q \le 10^5$ - $1 \le （树 X 的顶点数） \le 10^5$ - $1 \le （树 Y 的顶点数） \le 10^5$ 此问题没有部分分数，所有测试用例都通过可得满分 100 分。 **本翻译由 AI 自动生成**