CF1312G Autocompletion

给定一个 **仅包含小写字母的** 字符串集 $S$，你需要计算打出 $S$ 中的每个字符串需要花费的时间。 打一个字符串的步骤如下： 1. 从一个空串开始； 2. 如果当前的字符串是 $t$，你可以在 $t$ 的末尾拼接任意一个小写字母 $c$，使得此时字符串变为 $t + c$，这个过程耗费 $1$s； 3. 使用 **自动补全功能**，设当前字符串是 $t$，此时所有的 $s \in S$ 且 $t$ 是 $s$ 的前缀将会以 **字典序** 为你展现出来，其中你自动补全到第 $i$ 个串所耗费的时间为 $i$ s。 问打出 $S$ 中的所有字符串 **最短** 需要耗费多长时间。 **需要的注意的是 字符串集 $S$ 的给出方式**

第一行共一个整数 $n (1 \le n \le 10^6)$。 接下来的 $n$ 行，第 $i$ 行有一个整数 $p_i$ 和一个字符 $c_i$， 表示第 $i$ 个字符串是由第 $p_i$ 个字符串的末尾拼接上 $c$ 得到的。 接下来的一行共一个整数 $k (1 \le k \le n)$，表示字符串集 $S$ 的大小。 最后一行共 $k$ 个整数 $a_1, a_2, \cdots, a_k$，表示 $S = \{s_{a_1}, s_{a_2}, \cdots, s_{a_k}\}$。

一行共 $k$ 个整数 $b_1, b_2, \cdots, b_k$，分别表示打出 $s_{a_1}, s_{a_2}, \cdots, s_{a_k}$ 最短需要耗费的时间。 #### 样例解释 对于第一个样例，$S = \{\text{ieh}_8, \text{iqgp}_9, \text{i}_1, \text{iqge}_{10}, \text{ier}_6\}$（下标表示是第几个字符串） 需要注意的是，$\text{iqge}$ 可以使用两次拼接以及一次自动补全（选择列表里的第 $1$ 个）共 $3$s 完成；$\text{iqgp}$ 可以使用两次拼接以及一次自动补全（选择列表里的第 $2$ 个）共 $4$s 完成。

In the first example, $ S $ consists of the following strings: ieh, iqgp, i, iqge, ier.