题目详情题解（0）讨论（0）提交记录（0）

AT_ijpc2015_j.Верный

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

IOI2015 举办地阿拉木图，曾经被称为 Верный（维尔尼）。在俄语中，这个名字有「忠诚的」或「可信赖的」的意思。受此启发，joisino 决定测验一下她的下属对她的忠诚度。

为此，她准备了两棵树，分别命名为树 X 和树 Y。每棵树的顶点编号从 0 到 (树的顶点数−1)(树的顶点数 - 1)，且每个顶点上都有一个从 'a' 到 'j' 的小写字母。

接下来将执行 QQ 次操作：

  1. 在树 X 的某路径上，交换从 AA 到 BB 上（包括 AA 和 BB）的两个指定字母。例如，将 ′a′'a' 和 ′b′'b' 交换，会导致路径上的所有 ′a′'a' 变成 ′b′'b'，′b′'b' 变成 ′a′'a'。
  2. 在树 Y 的某路径上，交换从 AA 到 BB 上（包括 AA 和 BB）的两个指定字母。同样地，将 ′a′'a' 和 ′b′'b' 交换，会导致路径上的所有 ′a′'a' 变成 ′b′'b'，′b′'b' 变成 ′a′'a'。
  3. 比较树 X 上从 AA 到 BB 的路径（包括 AA 和 BB）上的字母组成的字符串，和树 Y 上从 CC 到 DD 的路径（包括 CC 和 DD）的字母组成的字符串，看它们是否相同。
  4. 回退到进行了 aa 次操作后的状态。这里 0≤a≤（当前已处理的操作次数）0 \le a \le （当前已处理的操作次数）。

输入格式

输入数据包括：

  1. 树 X 的数据
  2. 树 Y 的数据
  3. 查询次数 QQ
  4. 接下来的 QQ 个查询

每棵树的数据结构如下：

  • 首先，给出一个整数 NN，表示树的顶点数。
  • 接着是一串长度为 NN 的字符串 ss。其中第 i+1i+1 个字符表示顶点 ii 上的字母。
  • 随后的 N−1N-1 行，每行由两个整数 aia_i 和 bib_i 组成，表示在顶点 aia_i 和 bib_i 之间有一条边。

每个查询由以下格式组成：

  • 当查询类型 t=0t = 0 时，之后有整数 a,ba, b 和字符 c,dc, d。表示在树 X 的顶点 aa 到顶点 bb 之间，将所有 cc 替换为 dd，所有 dd 替换为 cc。
  • 当查询类型 t=1t = 1 时，结构与 t=0t = 0 相同，只不过是对树 Y 进行上述操作。
  • 当查询类型 t=2t = 2 时，之后有四个整数 a,b,c,da, b, c, d。表示判断树 X 上从 aa 到 bb 的路径上的字母组成的字符串，与树 Y 上从 cc 到 dd 的路径组成的字符串是否相同。
  • 当查询类型 t=3t = 3 时，有一个整数 aa。表示将两棵树的状态恢复到执行了 aa 次查询后的状态。

输出格式

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

输入输出样例

  • 输入#1

    4
ckdl
0 2
0 1
1 3
4
lckd
2 1
1 3
2 0
4
2 2 3 3 0
2 2 3 0 3
2 3 2 0 3
2 3 2 3 0

    输出#1

    YES
NO
YES
NO

说明/提示

  • 1≤Q≤1051 \le Q \le 10^5
  • 1≤（树X的顶点数）≤1051 \le （树 X 的顶点数） \le 10^5
  • 1≤（树Y的顶点数）≤1051 \le （树 Y 的顶点数） \le 10^5

此问题没有部分分数，所有测试用例都通过可得满分 100 分。

本翻译由 AI 自动生成

输入解题思路，AI测评打分。不知道怎么写?

首页