#P5439. 【XR-2】永恒

【XR-2】永恒

题目背景

我一直认为这世界没有永恒,如果非要说永恒,宇宙间唯一的永恒就是——所有的一切都会随着时光消失。——梧桐《那片星空,那片海》

题目描述

有一颗 nn 个点的永恒的树,树中每个点 x(1xn)x(1 \le x \le n) 上都有一个永恒的字符串 S(x)S(x)

但这世界没有永恒,所有的一切都会随着时光消失。我们只能给每个所谓永恒的东西定义一个永恒值 ff。这个值本身没有意义,只是一个象征罢了。

  • 一个字符串 SS 的永恒值 f(S)f(S) 定义为它的长度 Len(S)\mathrm{Len}(S),即:
f(S)=Len(S)f(S) = \mathrm{Len}(S)
  • 树上的一条无向路径 K=[u,v](u<v)K = [u, v](u < v) 指的是 u,vu,v 之间的简单路径(包括 u,vu, v),其永恒值 f(K)f(K) 定义为路径上所有不同的无序点对 (x,y)(xK,yK,x<y)(x, y)(x \in K, y \in K, x < y) 上的字符串 S(x),S(y)S(x), S(y) 的最长公共前缀 LCP(S(x),S(y))\mathrm{LCP}(S(x), S(y)) 的永恒值 f(LCP(S(x),S(y)))f(\mathrm{LCP}(S(x), S(y))) 之和,即:
$$f(K) = \sum_{x \in K, y \in K, x < y} f(\mathrm{LCP}(S(x), S(y))) $$
  • 一颗树 TT 的永恒值 f(T)f(T) 定义为树上所有的无向路径 [u,v](uT,vT,u<v)[u, v](u \in T, v \in T, u < v) 的永恒值之和,即:
f(T)=uT,vT,u<vf([u,v])f(T) = \sum_{u \in T, v \in T, u < v} f([u,v])

特别的是,树中每个点上的字符串都来自一颗永恒的以点 11 为根的 Trie 树,即每个树中的点都对应着一个 Trie 树中的点,点上的字符串就是 Trie 树中从根节点到其对应的点形成的字符串。

你需要求出这棵树的永恒值,答案对 998244353998244353 取模。

输入格式

第一行包含两个正整数 n,mn,m,分别表示树的节点数和 Trie 树的节点数。

第二行包含 nn 个非负整数,第 ii 个数为 aia_i,表示点 ii 在树上的父亲节点为 aia_i,对于树的根节点 rootroot,保证 aroot=0a_{root} = 0

第三行包含 mm 个非负整数,第 ii 个数为 bib_i,表示点 ii 在 Trie 树上的父亲节点为 bib_i,保证 bi<ib_i < ib1=0b_1=0

第四行为一个由 mm 个字符构成的字符串,第 ii 个字符 cic_i 表示 Trie 树上点 ii 与它的父亲节点 bib_i 之间的边所代表的字符,保证 c1=0c_1=\texttt{0}ci(2im)[a,z]c_i(2 \le i \le m)\in[\texttt{a},\texttt{z}]

第五行包含 nn 个正整数 did_i,表示树上的点 ii 对应着 Trie 树上的点 did_i,保证 2dim2 \le d_i \le m

输出格式

一行一个整数,表示答案对 998244353998244353 取模后的值。

3 17
2 0 2
0 1 2 3 4 5 6 7 8 4 10 11 12 3 14 15 16
0mayqueenkingrket
9 13 17

12

提示

【样例 11 说明】

所有的 S(x)S(x) 为:

S(1)="mayqueen"S(1) = \texttt{"mayqueen"}

S(2)="mayking"S(2) = \texttt{"mayking"}

S(3)="market"S(3) = \texttt{"market"}

所有的 f(LCP(S(x),S(y)))f(\mathrm{LCP}(S(x), S(y))) 为:

$f(\mathrm{LCP}(S(1), S(2))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"mayking"})) = f(\texttt{"may"}) = \mathrm{Len}(\texttt{"may"}) = 3$

$f(\mathrm{LCP}(S(1), S(3))) = f(\mathrm{LCP}(\texttt{"mayqueen"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

$f(\mathrm{LCP}(S(2), S(3))) = f(\mathrm{LCP}(\texttt{"mayking"}, \texttt{"market"})) = f(\texttt{"ma"}) = \mathrm{Len}(\texttt{"ma"}) = 2$

所有的 f([u,v])f([u, v]) 为:

f([1,2])=f(LCP(S(1),S(2)))=3f([1,2]) = f(\mathrm{LCP}(S(1), S(2))) = 3

$f([1,3]) = f(\mathrm{LCP}(S(1), S(2))) + f(\mathrm{LCP}(S(1), S(3))) + f(\mathrm{LCP}(S(2), S(3))) = 3 + 2 + 2 = 7$

f([2,3])=f(LCP(S(2),S(3)))=2f([2,3]) = f(\mathrm{LCP}(S(2), S(3))) = 2

所以:

$f(T) = f([1,2]) + f([2,3]) + f([1,3]) = 3 + 7 + 2 = 12$

【数据规模与约定】

本题采用捆绑测试。

Subtask 1(3 points):n,m10n, m \le 10,时限 1s。
Subtask 2(5 points):n,m100n, m \le 100,时限 1s。
Subtask 3(9 points):n,m1000n, m \le 1000,时限 1s。
Subtask 4(7 points):n,m5000n, m \le 5000,时限 2s。
Subtask 5(9 points):n,m20000n, m \le 20000,时限 3s。
Subtask 6(11 points):n,m105n, m \le 10^5,时限 4s。
Subtask 7(19 points):m=2m=2,时限 3s。
Subtask 8(37 points):无特殊限制,时限 10s。

对于 100%100\% 的数据,2n,m3×1052 \le n,m \le 3\times 10^5