← 返回题目列表

Codeforces · 207/C1

C1. 两棵树的游戏

中文机器翻译题面 查看原题

ABBYY 的智能海狸推出了一款新的儿童开发游戏。海狸认为这个游戏可以帮助孩子们更好地理解编程。

游戏的主要对象是有限根树,它们的每条边都包含一些小写英文字母。任何树上的顶点始终按从 1 到 m 的顺序编号,其中 m 是树中顶点的数量。在描述实际游戏之前,我们先介绍一些定义。

我们假设编号为 v1, v2, ..., vk (k ≥ 1) 的顶点序列是一条前向路径,如果对于从 1 到 k - 1 的任何整数 i,顶点 vi 是顶点 vi + 1 的直接祖先。如果我们顺序写出从 v1 到 vk 的给定路径的边上的所有字母,我们会得到一些字符串(k = 1 给我们一个空字符串)。我们会说这样的字符串对应于前向路径 v1, v2, ..., vk。

如果对于从 1 到 k - 1 的任何整数 i,顶点 vi 是顶点 vi + 1 的直系后代,我们假设具有数字 v1、v2、...、vk (k ≥ 1) 的树顶点序列是后向路径。如果我们顺序写出从 v1 到 vk 的给定路径的边上的所有字母,我们会得到一些字符串(k = 1 给我们一个空字符串)。我们会说这样的字符串对应于后向路径 v1, v2, ..., vk。

现在让我们来描述一下 ABBYY 的 Smart Beaver 推出的游戏。游戏使用两棵有根树,每棵树最初都由一个编号为 1 的顶点组成。玩家将获得一定的操作序列。每个操作都由三个值 (t、v、c) 表征,其中:

- t 是执行操作的树的编号(1 或 2);
- v 是该树中的顶点索引(保证该树包含具有该索引的顶点);
- c 是小写英文字母。

实际操作如下:树t的顶点v得到一个编号为m+1的新后代(其中m是树t中当前的顶点数),并且在从顶点v到顶点m+1的新边上应该放置字母c。

如果满足以下条件,我们会说三个整数 (i, j, q) 的有序组是一个很好的组合:

- 1 ≤ i ≤ m1,其中m1是第一棵树的顶点数;
- 1 ≤ j, q ≤ m2,其中m2是第二棵树的顶点数;
- 在第二棵树中存在前向路径 v1, v2, ..., vk 使得 v1 = j 且 vk = q;
- 对应于第二棵树中从顶点 j 到顶点 q 的前向路径的字符串等于对应于第一棵树中从顶点 i 到顶点 1 的后向路径的字符串(请注意,两条路径都是唯一确定的)。

您的任务是在对树进行每次操作后计算现有的良好组合的数量。

输入

第一行包含整数 n — 树上的操作数。接下来的 n 行按照执行顺序指定操作。每行的形式为“t v c”,其中t是树的编号,v是这棵树中的顶点索引,c是小写英文字母。

要获得第一组测试的满分,解决 1 ≤ n ≤ 700 的问题就足够了。

要获得第二组测试的满分,解决 1 ≤ n ≤ 7000 的问题就足够了。

要获得第三组测试的满分,解决 1 ≤ n ≤ 100000 的问题就足够了。

输出

精确打印 n 行,每行包含一个整数 — 从输入进行相应操作后现有的良好组合的数量。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

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

输出 #1

1
3
3
4
7

注意

第一次操作后,唯一好的组合是 (1, 1, 1)。第二次操作后,出现了新的良好组合,(2,1,2)和(1,2,2)。第三次手术并没有带来什么好的组合。第四次操作添加了良好的组合(1,3,3)。最后,第五次操作产生了多达三个新的良好组合——(1,4,4)、(2,3,4)和(3,1,4)。