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 完成。

题目描述

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.

输入输出格式

输入格式

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 < 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}} $ .

输出格式

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} $ .

输入输出样例

输入样例 #1

10
0 i
1 q
2 g
0 k
1 e
5 r
4 m
5 h
3 p
3 e
5
8 9 1 10 6

输出样例 #1

2 4 1 3 3

输入样例 #2

8
0 a
1 b
2 a
2 b
4 a
4 b
5 c
6 d
5
2 3 4 7 8

输出样例 #2

1 2 2 4 4

说明

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