SP3581 TREESIM - Tree Similarity

给你两棵有标记的有序有根树 $T$ 和 $T'$，需要计算将 $T$ 转变为与 $T'$ 等价所需的最小操作次数。每次可以进行以下操作之一： 1. 修改 $T$ 中某个节点的标签。 2. 删除 $T$ 中的一个非根节点。 3. 在 $T$ 中根节点的某个子节点位置插入新节点。 注意，树 $T$ 和 $T'$ 是有序的，这意味着对于一个非叶节点而言，如果它有 $c$ 个子节点，那么这些子节点有明确的顺序，从第 1 个到第 $c$ 个。两棵树等价意味着以下三点：$X$ 的根节点标签要与 $Y$ 的根节点标签相同；两者的根节点子节点数相同；对于任意 $i = 1, 2, \ldots, c$，$X$ 的根节点第 $i$ 个子节点构成的子树应该与 $Y$ 的根节点第 $i$ 个子节点构成的子树等价。 我们来说明删除和插入非根节点的具体方法。当删除一个非根节点 $w$ 时，若 $w$ 有 $d$ 个子节点，设其父节点是 $u$，并假定 $w$ 是 $u$ 的第 $i$ 个子节点。那么，$w$ 的第一个子节点将成为 $u$ 的第 $i$ 个子节点，$w$ 的第二个子节点成为 $u$ 的第 $(i+1)$ 个子节点，依此类推。对于 $j < i$，$u$ 的第 $j$ 个子节点保持不变，而对于所有 $j > i$，原先 $u$ 的第 $j$ 个子节点将变为第 $(j+d-1)$ 个子节点（因为 $w$ 的子节点插入到 $u$ 的子节点列表中导致其“向后移动”）。插入非根节点时，可以选择任意节点 $u$ 作为其父节点，并选择 $u$ 的任意连续子序列（可以为空）作为新节点 $w$ 的子节点，将 $w$ 插入到这些子节点的位置。插入时可以为节点赋予任意标签。根节点不能删除，也不能在根节点上方插入一个新的节点作为其父节点，但可以修改根节点的标签。

第一行包含两个整数 $n$ 和 $m$，代表树 $T$ 和 $T'$ 的大小（$1 \leq n, m \leq 60$）。接下来的 $n$ 行描述树 $T$。每一行描述一个节点：节点的标签、子节点的数量，随后是按顺序的子节点编号，每个部分用空格分隔。随后 $m$ 行以相同格式描述树 $T'$。

输出一行，表示将 $T$ 变为与 $T'$ 等价的最小操作次数，最后需换行。 **本翻译由 AI 自动生成**