Pty的字符串
时间限制:20s 空间限制:512MB
题目描述
在神秘的东方有一棵奇葩的树,它有一个固定的根节点(编号为1)。树的每条边上都是一个字符,字符为a,b,c中的一个,你可以从树上的任意一个点出发,然后沿着远离根的边往下行走,在任意一个节点停止,将你经过的边的字符依次写下来,就能得到一个字符串,例如:
![](https://pic.taifua.com/cdn/bzoj/file/3756_0.gif)
在这棵树中我们能够得到的字符串是:
c, cb, ca, a, b, a
现在pty得到了一棵树和一个字符串S。如果S的一个子串[l,r]和树上某条路径所得到的字符串完全相同,则我们称这个子串和该路径匹配。现在pty想知道,S的所有子串和树上的所有路径的匹配总数是多少?
输入格式
第一行:n
接下来n-1行,每行一个整数fa, 一个字符c,字符和整数之间用一个空格隔开
第i行fa代表第i号节点的父亲,c表示第i号节点和fa的连边的字符
最后一行为字符串S
输出格式
输出共一行,表示匹配总数
样例输入
5 1 c 2 b 1 a 2 a cba
样例输出
5 【样例说明】 单个字符匹配的对数为4对,两个字符匹配的对数为1对:cb
提示
【数据规模】
N<=800000 树的最大深度<=800000
此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!
题目来源
没有写明来源