给定字符串 ，令 表示前缀 。特别地， 是空字符串。
对于两个字符串 与 ，令 表示连接后的字符串 。
给定长度为 的字符串 和一棵有 个节点的树 ，节点编号为 ，其中节点 是根。每条边上都有一个字符。请注意，在本题中，字母表中可能会有多于 个字符。
考虑如下函数 f(i,j) = \max{d(x) \mid s_x\text{ 是 }s_i+ \mathrm{pre}(t,j)\text{ 的后缀}} 其中 是从根到节点 的最短路径上所有字符连接而成的字符串， 是从根到节点 的最短路径经过的边数。
您需要计算 ，其中 。
请注意， 是空字符串，空字符串是任何字符串的后缀。
