CF207C3 Game with Two Trees

ABBYY 的聪明海狸发明了一款新的儿童益智游戏。海狸认为这款游戏能帮助孩子们更好地理解编程。 游戏的主要对象是有限有根树，每条边上都标有一个小写英文字母。每棵树的顶点总是从 $1$ 到 $m$ 顺序编号，其中 $m$ 是树中顶点的数量。在介绍实际游戏之前，先给出一些定义。 我们认为，顶点序列 $v_{1}$、$v_{2}$、$\ldots$、$v_{k}$（$k \geq 1$）是一个“正向路径”，如果对于任意整数 $i$，$1 \leq i < k$，顶点 $v_{i}$ 是顶点 $v_{i+1}$ 的直接祖先。如果我们依次写出该路径上从 $v_{1}$ 到 $v_{k}$ 的所有边上的字母，就得到一个字符串（$k=1$ 时为空串）。我们称这个字符串为该正向路径 $v_{1}$、$v_{2}$、$\ldots$、$v_{k}$ 所对应的字符串。 我们认为，顶点序列 $v_{1}$、$v_{2}$、$\ldots$、$v_{k}$（$k \geq 1$）是一个“反向路径”，如果对于任意整数 $i$，$1 \leq i < k$，顶点 $v_{i}$ 是顶点 $v_{i+1}$ 的直接子节点。如果我们依次写出该路径上从 $v_{1}$ 到 $v_{k}$ 的所有边上的字母，就得到一个字符串（$k=1$ 时为空串）。我们称这个字符串为该反向路径 $v_{1}$、$v_{2}$、$\ldots$、$v_{k}$ 所对应的字符串。 现在介绍 ABBYY 的聪明海狸设计的游戏。游戏中有两棵有根树，每棵树初始时都只有编号为 $1$ 的一个顶点。玩家会得到一系列操作。每个操作由三个值 $(t, v, c)$ 描述，其中： - $t$ 表示进行操作的树的编号（$1$ 或 $2$）； - $v$ 表示该树中的顶点编号（保证该树中存在编号为 $v$ 的顶点）； - $c$ 是一个小写英文字母。 具体操作如下：在树 $t$ 的顶点 $v$ 下添加一个新的子节点，编号为 $m+1$（$m$ 是当前树 $t$ 的顶点数），并在从 $v$ 到 $m+1$ 的新边上标记字母 $c$。 我们称有序三元组 $(i, j, q)$ 为一个“好组合”，如果满足： - $1 \leq i \leq m_{1}$，其中 $m_{1}$ 是第一棵树的顶点数； - $1 \leq j, q \leq m_{2}$，其中 $m_{2}$ 是第二棵树的顶点数； - 在第二棵树中，存在一个正向路径 $v_{1}, v_{2}, \ldots, v_{k}$，使得 $v_{1}=j$，$v_{k}=q$； - 第二棵树中从顶点 $j$ 到 $q$ 的正向路径所对应的字符串，等于第一棵树中从顶点 $i$ 到 $1$ 的反向路径所对应的字符串（注意这两条路径都是唯一确定的）。 你的任务是，在每次操作后，计算当前存在的好组合的数量。

第一行包含一个整数 $n$，表示对树进行的操作数。接下来的 $n$ 行按顺序给出每次操作。每行格式为“$t$ $v$ $c$”，其中 $t$ 是树的编号，$v$ 是该树中的顶点编号，$c$ 是一个小写英文字母。 对于第一组测试数据，$1 \leq n \leq 700$。 对于第二组测试数据，$1 \leq n \leq 7000$。 对于第三组测试数据，$1 \leq n \leq 100000$。

输出恰好 $n$ 行，每行一个整数，表示在对应操作后存在的好组合数量。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。推荐使用 cin、cout 流或 %I64d 格式。

第一次操作后，唯一的好组合是 $(1,1,1)$。第二次操作后出现了新的好组合，$(2,1,2)$ 和 $(1,2,2)$。第三次操作没有带来新的好组合。第四次操作增加了好组合 $(1,3,3)$。最后，第五次操作带来了多达三个新好组合——$(1,4,4)$、$(2,3,4)$ 和 $(3,1,4)$。 由 ChatGPT 4.1 翻译