#P3467. Crash和陶陶的游戏

    ID: 2680 传统题 2000ms 256MiB 尝试: 52 已通过: 14 难度: 7 上传者: 标签>字符串字符串哈希数据结构树状数组排序与序列处理倍增组合数学CF2200字典树前缀和

Crash和陶陶的游戏

Crash 和陶陶的游戏

题目描述

Crash 和陶陶各有一棵有根树,每条边标有一个小写英文字母。把 Crash 的树上从节点 ss 走到节点 tt 的唯一路径上的字母按经过顺序连起来,记作 As→tA_{s\to t}。同样,陶陶的树上的路径字符串记作 Bs→tB_{s\to t}。起点和终点相同时字符串为空。路径的读取方向会影响字符串。

开始时,两棵树都只有编号为 11 的根节点。之后有 NN 次操作,每次在其中一棵树上添加一个节点。若这棵树在操作前有 mm 个节点,则新节点的编号是 m+1m+1。操作指定新节点的父节点,以及连接这两个节点的边的字母。

每次操作后,统计满足以下条件的三元组 (i,j,k)(i,j,k) 的个数。

  1. ii 是 Crash 当前树中的节点。
  2. j,kj,k 都是陶陶当前树中的节点。
  3. 在陶陶的树中,jj 是 kk 的祖先,或者 j=kj=k。
  4. A1→i=Bk→jA_{1\to i}=B_{k\to j}。

输入格式

第一行包含一个正整数 NN,表示操作数,N≤105N\le 10^5。

接下来 NN 行,每行包含两个整数 T,VT,V 和一个小写英文字母 CC。T=1T=1 表示在 Crash 的树上操作,T=2T=2 表示在陶陶的树上操作。VV 是新节点的父节点编号,CC 是新边上的字母。数据保证所有操作合法。

输出格式

输出 NN 行。每行输出对应操作后的三元组数。

样例 #1

5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a
1
3
3
4
7