QOJ.ac

QOJ

Time Limit: 3.5 s Memory Limit: 1024 MB Total points: 100

# 8630. 字符树

Statistics

题目描述

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

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

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

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

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

输入格式

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

之后一行包含 $n-1$ 个数,第 $i$ 个数表示第 $i+1$ 个点的父亲 $f_{i+1}$,保证每个点父亲的编号比这个点的编号小。

之后一行包含 $n-1$ 个字符,第 $i$ 个字符表示第 $i+1$ 个点到父亲的边上的字符 $a_{i+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\%$ 的数据,满足 $1\le n,m\le 250$。

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

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

对于另外 $10\%$ 的数据,满足 $X\le 3$。

对于另外 $10\%$ 的数据,满足 $X\ge 20000$。

对于另外 $10\%$ 的数据,满足 $f_i=i-1$。

对于另外 $10\%$ 的数据,满足 $a_i\le 1$。

对于另外 $10\%$ 的数据,满足 $1\le n,m\le 2.5\times 10^4$,$mX\le 2.5\times 10^4$。

对于另外 $10\%$ 的数据,满足 $1\le n,m\le 2.5\times 10^5$,$mX\le 2.5\times 10^5$。

对于 $100\%$ 的数据,满足 $1\le n,m,X\le 5\times 10^5$,字符集为 $[1,9]$ 以内的整数,$mX\le 5\times 10^5$。