## Metropolis

先考虑单次询问怎么做。

括号串可以被翻译成一个出边有顺序的有根森林（或者加一个虚根之后变成有根树），于是我们的问题可以被重新描述成：

- 给定两棵（出边有顺序的）有根树 $T_A,T_B$，问能否从 $T_A$ 中删去一些结点，并将每个结点的父亲重设为最深的未被删除的祖先，得到 $T_B$。

对于树 $T$ 上的一个点 $x$，它的儿子按顺序分别为 $y_1,\ldots,y_k$，我们将形如 $\operatorname{Subtree}(y_l)\cup \cdots \cup \operatorname{Subtree}(y_r)$ 的结构称为一个**子树区间**，记为 $I(x,l,r)$。如果 $l=1$ 则称为**子树前缀**，如果 $r=k$ 则称为**子树后缀**。

下面考虑如何从 $T_A$ 生成 $T_B$，首先根结点一定是应该对应的（如果对应 $T_B$ 根的不是 $T_A$ 的根，那么一定可以调整成根）。

然后我们看根的子结点。设 $T_A$ 的根 $r_A$ 的子结点按顺序为 $x_1,\ldots,x_a$，$T_B$ 的根 $r_B$ 的子结点按顺序为 $y_1,\ldots,y_b$，那么不难证明每个 $x_i$ 会生成 $T_B$ 中一个子树区间 $I(r_B,l_i,r_i)$，最终每个 $x_i$ 生成的子树区间并起来就是所有的 $\operatorname{Subtree}(y_i)$。

如果 $x_i$ 可以生成 $I(r_B,l,r)$，那么对于所有的 $[l',r']\subseteq [l,r]$，$x_i$ 也一定能生成 $I(r_B,l',r')$。因此我们有一个贪心：依次枚举 $x_1,\ldots,x_a$，每次用当前的 $x_i$ 匹配一个尽量长的子树区间，如果结束时能匹配完最后一个子树 $y_b$，就说明可以生成。

所以现在的问题是如何求出 $x_i$ 能生成的一个（给定 $l$ 的）尽量长（$r$ 最大的）的子树区间 $I(r_B,l,r)$。可以发现生成的方式只有两种：

- 一种是不删除 $x_i$，直接用 $\operatorname{Subtree}(x_i)$ 生成 $I(r_B,l,l)=\operatorname{Subtree}(y_l)$，如下图：

![](pic1.png)

- 一种是删除 $x_i$，用 $x_i$ 的各个子树生成 $I(r_B,l,r)$，如下图，同种颜色的框内的子树/子树区间为生成关系：

![](pic2.png)

不管是哪种情况，都是一个递归过程。我们可以整理成如下过程：

记 $\operatorname{Check}(u,v)$ 表示判定 $T_A$ 中 $u$ 的子树能否生成 $T_B$ 中 $v$ 的子树；$\operatorname{Cover}(u,v,l)$ 表示求最大的 $r$ 使得 $T_A$ 中 $u$ 的子树能生成 $T_B$ 中的 $I(v,l,r)$。再记 $deg_u$ 表示 $u$ 的子结点数量。

$\operatorname{Check}(u,v)$ 过程如下：

- 设 $x_1,\ldots,x_a$ 分别为 $u$ 的所有子结点（$a=deg_u$）；$y_1,\ldots,y_b$ 分别为 $v$ 的所有子结点（$b=deg_v$）。

- 初始令 $cur=1$，然后依次遍历 $x_i\leftarrow x_1,\ldots,x_a$，直到遍历完毕或 $cur=b+1$：
  
  - 令 $cur=\operatorname{Cover}(x_i,v,cur)+1$。

- 若 $cur=b+1$，则返回 $\operatorname{True}$，否则返回 $\operatorname{False}$。

$\operatorname{Cover}(u,v,l)$ 过程如下：

- 设 $x_1,\ldots,x_a$ 分别为 $u$ 的所有子结点（$a=deg_u$）；$y_1,\ldots,y_b$ 分别为 $v$ 的所有子结点（$b=deg_v$）。

- 初始令 $cur=l$，然后依次遍历 $x_i\leftarrow x_1,\ldots,x_a$，直到遍历完毕或 $cur=b+1$：
  
  - 令 $cur=\operatorname{Cover}(x_i,v,cur)+1$。

- 若 $cur>l$，则返回 $cur-1$，否则：

  - 若 $\operatorname{Check}(u,v)$，则返回 $l$；否则返回 $l-1$。

从下往上计算或记忆化搜索，上述两个过程的复杂度均为 $O(deg_u)$，对于每个 $u$ 有 $O(m)$ 种状态（因为子树后缀的数量是 $O(m)$ 的），因此总复杂度为 $O(\sum deg_u\times m)=O(nm)$。

再考虑多组询问，不难发现每组询问给出的就分别是 $T_A,T_B$ 上的子树区间 $I(x,l,r)$ 和 $I(y,l',r')$，我们可以类似 $\operatorname{Check}$ 过程地 $O(r-l+1)$ 地回答询问，而 $r-l+1\leq n$，所以单次询问复杂度是 $O(n)$。

总复杂度 $O(nm+nq)$。

倍增一下应该就可以 $O(\log n)$ 回答询问了，但是感觉没啥意义而且会增加预处理复杂度，所以本题没有这样要求。