给你一棵有 N 个节点的有根树。每个节点包含一个小写英文字母。标签为 1 的节点是根。 有形式的Q题， X S:这里X是子树的根，S是字符串。
对于每个问题，令 T 为使用根为 X 的子树节点中的所有字符构建的字符串(每个子树节点字符恰好出现一次)。 对于每个问题，打印要添加到 T 的最少字符数，以便我们可以使用字符串 T 的一些字符构建 S (字符串T的每个字符最多只能使用一次)。
输入格式:
第一行输入由两个空格分隔的整数组成 N 和 Q 分别是树中的节点数和问题数。 下一行将包含 N 个空格分隔的小写英文字母，其中第 i 个字母将是存储在标签为 i 的节点中的字母。 接下来的 N-1 行中的每一行都包含两个空格分隔的整数 u 和 v 表示标签为 u 和 v 的节点之间有一条边 接下来是 Q 行。每行将包含一个整数 X 表示节点标签和字符串 S 由一个空格分隔。
输出格式:
对于每个查询，在新行中打印所需的答案。
输入约束 2≤N≤105 1≤Q≤105 1≤u,v≤N;u!=v 1≤X≤N
节点和字符串中的所有字符均为小写英文字母。 所有问题的字符串长度之和最多为10^6
示例输入
8 3
o v s l v p d i
1 3
8 3
4 8
6 1
5 3
7 6
2 3
7 ifwrxl
4 爱丽丝
3 岁
示例输出:
6
7
2
解释
查询 1- 根为 7 的子树中的字符为 d，我们需要 6 字符 (i,f,w,r,x,l) 使 S=(ifwrxl)。
查询 2- 根节点为 4 的子树中的字符是 l，我们需要 7 个字符 (e,y,j,y,w,n,m) 使 S=(eyljywnm)。
查询 3- 根节点为 3 的子树中的字符是 (v,s,i,l)，我们需要 2 个字符 (l,e) 来使 S=(llvse)。
最佳答案
我们可以使用带有head, down pointer, left pointer 的Multilevel Linklist 来维护节点级别。并将查询给定的节点迭代到多级链表中，然后将查询字符串与向下指针节点进行比较。
关于algorithm - 从子树中查找所需的最少字符，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/48780273/