Game with Two Trees

题意翻译

定义有根树 $T$ 上点 $u$ 的深度为从根到 $v$ 所经过的边数。 定义**边带字符的有根树** $T$ 上的一条向根串 $S_T(i,l)$ 为从点 $i$ 开始，向根的 $l$ 条边上的字符按顺序组成的字符串。$l$ **可以为零**，此时即为空串。但 $l$ 不能超过点 $u$ 的深度。 有两个**边带字符的有根树** $t_1,t_2$，定义其点数为 $n_1,n_2$，初始时**只有根**，编号为 $1$。 共 $q$ 次操作，每次操作给出所操作树的编号 $p$（$p\in\{1,2\}$）、所操作点的编号 $u$（$1\le u\le n$）和字符 $c$，表示在 $t_p$ 中编号为 $u$ 的点下面加一个孩子，编号为操作前的 $n_p+1$，而 $u$ 到该孩子的边上的字符为 $c$。此后 $n_p$ 将自增 $1$。 每次操作完后，请求出 $(i,j)$（$1\le i\le n_1,\le j\le n_2$）的对数，定义 $l$ 为 $t_1$ 中 $i$ 的深度，使得 $S_{t_1}(i,l)$ 与**翻转后的** $S_{t_2}(j,l)$ 相同。 字符集为小写英文字母。 注意：对于 C1，C2，C3 三个子任务，$q$ 范围不同。 对 C1，$1\le q\le700$；对 C2，$1\le q\le7000$；对 C3，$1\le q\le100000$。

题目描述

The Smart Beaver from ABBYY has come up with a new developing game for children. The Beaver thinks that this game will help children to understand programming better. The main object of the game is finite rooted trees, each of their edges contains some lowercase English letter. Vertices on any tree are always numbered sequentially from $ 1 $ to $ m $ , where $ m $ is the number of vertices in the tree. Before describing the actual game, let's introduce some definitions. We'll assume that the sequence of vertices with numbers $ v_{1} $ , $ v_{2} $ , $ ... $ , $ v_{k} $ ( $ k>=1 $ ) is a forward path, if for any integer $ i $ from $ 1 $ to $ k-1 $ vertex $ v_{i} $ is a direct ancestor of vertex $ v_{i+1} $ . If we sequentially write out all letters from the the edges of the given path from $ v_{1} $ to $ v_{k} $ , we get some string ( $ k=1 $ gives us an empty string). We'll say that such string corresponds to forward path $ v_{1} $ , $ v_{2} $ , $ ... $ , $ v_{k} $ . We'll assume that the sequence of tree vertices with numbers $ v_{1} $ , $ v_{2} $ , $ ... $ , $ v_{k} $ ( $ k>=1 $ ) is a backward path if for any integer $ i $ from $ 1 $ to $ k-1 $ vertex $ v_{i} $ is the direct descendant of vertex $ v_{i+1} $ . If we sequentially write out all the letters from the edges of the given path from $ v_{1} $ to $ v_{k} $ , we get some string ( $ k=1 $ gives us an empty string). We'll say that such string corresponds to backward path $ v_{1} $ , $ v_{2} $ , $ ... $ , $ v_{k} $ . Now let's describe the game that the Smart Beaver from ABBYY has come up with. The game uses two rooted trees, each of which initially consists of one vertex with number $ 1 $ . The player is given some sequence of operations. Each operation is characterized by three values ( $ t $ , $ v $ , $ c $ ) where: - $ t $ is the number of the tree on which the operation is executed ( $ 1 $ or $ 2 $ ); - $ v $ is the vertex index in this tree (it is guaranteed that the tree contains a vertex with this index); - $ c $ is a lowercase English letter. The actual operation is as follows: vertex $ v $ of tree $ t $ gets a new descendant with number $ m+1 $ (where $ m $ is the current number of vertices in tree $ t $ ), and there should be letter $ c $ put on the new edge from vertex $ v $ to vertex $ m+1 $ . We'll say that an ordered group of three integers ( $ i $ , $ j $ , $ q $ ) is a good combination if: - $ 1<=i<=m_{1} $ , where $ m_{1} $ is the number of vertices in the first tree; - $ 1<=j,q<=m_{2} $ , where $ m_{2} $ is the number of vertices in the second tree; - there exists a forward path $ v_{1} $ , $ v_{2} $ , $ ... $ , $ v_{k} $ such that $ v_{1}=j $ and $ v_{k}=q $ in the second tree; - the string that corresponds to the forward path in the second tree from vertex $ j $ to vertex $ q $ equals the string that corresponds to the backward path in the first tree from vertex $ i $ to vertex $ 1 $ (note that both paths are determined uniquely). Your task is to calculate the number of existing good combinations after each operation on the trees.

输入输出格式

输入格式

The first line contains integer $ n $ — the number of operations on the trees. Next $ n $ lines specify the operations in the order of their execution. Each line has form " $ t $ $ v $ $ c $ ", where $ t $ is the number of the tree, $ v $ is the vertex index in this tree, and $ c $ is a lowercase English letter. To get the full points for the first group of tests it is sufficient to solve the problem with $ 1<=n<=700 $ . To get the full points for the second group of tests it is sufficient to solve the problem with $ 1<=n<=7000 $ . To get the full points for the third group of tests it is sufficient to solve the problem with $ 1<=n<=100000 $ .

输出格式

Print exactly $ n $ lines, each containing one integer — the number of existing good combinations after the corresponding operation from the input. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a

输出样例 #1

1
3
3
4
7

说明

After the first operation the only good combination was $ (1,1,1) $ . After the second operation new good combinations appeared, $ (2,1,2) $ and $ (1,2,2) $ . The third operation didn't bring any good combinations. The fourth operation added good combination $ (1,3,3) $ . Finally, the fifth operation resulted in as much as three new good combinations — $ (1,4,4) $ , $ (2,3,4) $ and $ (3,1,4) $ .