#P3467. Crash和陶陶的游戏
Crash和陶陶的游戏
Crash 和陶陶的游戏
题目描述
Crash 和陶陶各有一棵有根树,每条边标有一个小写英文字母。把 Crash 的树上从节点 走到节点 的唯一路径上的字母按经过顺序连起来,记作 。同样,陶陶的树上的路径字符串记作 。起点和终点相同时字符串为空。路径的读取方向会影响字符串。
开始时,两棵树都只有编号为 的根节点。之后有 次操作,每次在其中一棵树上添加一个节点。若这棵树在操作前有 个节点,则新节点的编号是 。操作指定新节点的父节点,以及连接这两个节点的边的字母。
每次操作后,统计满足以下条件的三元组 的个数。
- 是 Crash 当前树中的节点。
- 都是陶陶当前树中的节点。
- 在陶陶的树中, 是 的祖先,或者 。
- 。
输入格式
第一行包含一个正整数 ,表示操作数,。
接下来 行,每行包含两个整数 和一个小写英文字母 。 表示在 Crash 的树上操作, 表示在陶陶的树上操作。 是新节点的父节点编号, 是新边上的字母。数据保证所有操作合法。
输出格式
输出 行。每行输出对应操作后的三元组数。
样例 #1
5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a
1
3
3
4
7