QOJ.ac

QOJ

Time Limit: 3.5 s Memory Limit: 1024 MB Total points: 100
[0]

# 8630. 字符树

Statistics

题目描述

给定一棵树,树上的每条边上有一个字符。给定一个常数 X

有两种操作,每次操作输入三个整数与一个字符串:

1 x y S:对于 xy 的有向简单路径上的边,将路径上的第 i 条边上的字符替换为 S 上的对应字符 Si,保证这条 xy 之间路径的边数为 X

2 x y S:查询 xy 构成的有向简单路径所形成的字符串上,S 匹配的次数(这里的匹配即:将 S 当做模式串,在这条路径构成的字符串上逐位置匹配。)例如:S=121 ,路径上的字符串为 1212122,则匹配了2次,分别在第 [1,3] 处和[3,5] 处。

上述所有字符串 S 的下标从 1 开始,保证每个输入的字符串长度均为 X

输入格式

第一行三个以空格分隔的整数 n,m,X

之后一行包含 n1 个数,第 i 个数表示第 i+1 个点的父亲 fi+1,保证每个点父亲的编号比这个点的编号小。

之后一行包含 n1 个字符,第 i 个字符表示第 i+1 个点到父亲的边上的字符 ai+1

之后 m 行,每行输入以空格隔开的三个整数 opt,x,y 与一个长为 X 的字符串 S,表示一次操作。

输出格式

若干行,每行一个整数,表示每次 2 操作的答案。

样例

输入

10 7 2
1 2 3 2 3 3 3 3 7
212111121
2 1 4 21
1 10 3 21
1 9 7 22
2 2 10 12
2 6 8 11
1 9 8 12
2 4 7 11

输出

1
1
1
0

子任务

对于 10% 的数据,满足 1n,m250

对于另外 10% 的数据,不存在 1 操作。

对于另外 10% 的数据,满足 X=1

对于另外 10% 的数据,满足 X3

对于另外 10% 的数据,满足 X20000

对于另外 10% 的数据,满足 fi=i1

对于另外 10% 的数据,满足 ai1

对于另外 10% 的数据,满足 1n,m2.5×104mX2.5×104

对于另外 10% 的数据,满足 1n,m2.5×105mX2.5×105

对于 100% 的数据,满足 1n,m,X5×105,字符集为 [1,9] 以内的整数,mX5×105