CF1312G.Autocompletion

You are given a set of strings $S$. Each string consists of lowercase Latin letters.

For each string in this set, you want to calculate the minimum number of seconds required to type this string. To type a string, you have to start with an empty string and transform it into the string you want to type using the following actions:

• if the current string is $t$, choose some lowercase Latin letter $c$ and append it to the back of $t$, so the current string becomes $t + c$. This action takes $1$ second;
• use autocompletion. When you try to autocomplete the current string $t$, a list of all strings $s \in S$ such that $t$ is a prefix of $s$ is shown to you. This list includes $t$ itself, if $t$ is a string from $S$, and the strings are ordered lexicographically. You can transform $t$ into the $i$-th string from this list in $i$ seconds. Note that you may choose any string from this list you want, it is not necessarily the string you are trying to type.

What is the minimum number of seconds that you have to spend to type each string from $S$?

Note that the strings from $S$ are given in an unusual way.

给你一个字符串集合 $S$，其中每个字符串均由小写拉丁字母组成。

对于该集合中的每个字符串，你需要计算出输入该字符串所需的最少秒数。输入一个字符串时，你必须从一个空字符串开始，并通过以下操作将其变换为你想要输入的字符串：

• 若当前字符串为 $t$，则可以选择某个小写拉丁字母 $c$，并将 $c$ 追加到 $t$ 的末尾，使当前字符串变为 $t + c$。此操作耗时 $1$ 秒；
• 使用自动补全功能。当你尝试对当前字符串 $t$ 进行自动补全时，系统会向你展示所有满足“$t$ 是 $s$ 的前缀”的字符串 $s \in S$ 构成的列表。该列表包含 $t$ 本身（若 $t \in S$），且列表中的字符串按字典序排列。你可以用 $i$ 秒将 $t$ 变换为该列表中第 $i$ 个字符串（$i$ 从 $1$ 开始计数）。注意：你可以选择列表中任意一个字符串，不一定是你最终想要输入的目标字符串。

请问：输入集合 $S$ 中每个字符串所需的最少秒数分别是多少？

注意：集合 $S$ 中的字符串是以一种特殊方式给出的。

The first line contains one integer $n$ ($1 \le n \le 10^6$).

Then $n$ lines follow, the $i$-th line contains one integer $p_i$ ($0 \le p_i \lt i$) and one lowercase Latin character $c_i$. These lines form some set of strings such that $S$ is its subset as follows: there are $n + 1$ strings, numbered from $0$ to $n$; the $0$-th string is an empty string, and the $i$-th string ($i \ge 1$) is the result of appending the character $c_i$ to the string $p_i$. It is guaranteed that all these strings are distinct.

The next line contains one integer $k$ ($1 \le k \le n$) — the number of strings in $S$.

The last line contains $k$ integers $a_1$, $a_2$, ..., $a_k$ ($1 \le a_i \le n$, all $a_i$ are pairwise distinct) denoting the indices of the strings generated by above-mentioned process that form the set $S$ — formally, if we denote the $i$-th generated string as $s_i$, then $S = {s_{a_1}, s_{a_2}, \dots, s_{a_k}}$.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。

接下来有 $n$ 行，第 $i$ 行包含一个整数 $p_i$（$0 \le p_i \lt i$）和一个小写拉丁字母 $c_i$。这些行定义了某个字符串集合，其中 $S$ 是该集合的一个子集，具体定义如下：共有 $n + 1$ 个字符串，编号从 $0$ 到 $n$；第 $0$ 个字符串为空字符串；对于 $i \ge 1$，第 $i$ 个字符串由将字符 $c_i$ 追加到字符串 $p_i$ 后得到。保证所有这些字符串互不相同。

下一行包含一个整数 $k$（$1 \le k \le n$）——即集合 $S$ 中字符串的个数。

最后一行包含 $k$ 个整数 $a_1$, $a_2$, ..., $a_k$（$1 \le a_i \le n$，且所有 $a_i$ 两两不同），表示由上述过程生成的字符串中属于集合 $S$ 的那些字符串的下标。形式化地说，若记第 $i$ 个生成的字符串为 $s_i$，则 $S = \{s_{a_1}, s_{a_2}, \dots, s_{a_k}\}$。

Print $k$ integers, the $i$-th of them should be equal to the minimum number of seconds required to type the string $s_{a_i}$.

输出 $k$ 个整数，其中第 $i$ 个整数应等于输入字符串 $s_{a_i}$ 所需的最少秒数。

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

在第一个例子中，$S$ 包含以下字符串：ieh、iqgp、i、iqge、ier。