Autocompletion
Contest: Educational Codeforces Round 83 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, dfs and similar, dp

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.

Input format:
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}}$$$.

Output format:
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}$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
2 4 1 3 3

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

Example output:
1 2 2 4 4

Editorial:
First of all, the information given in the input is the structure of a trie built on $$$S$$$ and some other strings — so we can store this information in the same way as we store a trie.
Okay, now let's calculate the number of seconds required to type each string with dynamic programming: let $$$dp_i$$$ be the number of seconds required to arrive to the $$$i$$$-th vertex of the trie. For regular vertices, $$$dp_i = dp_{p_i} + 1$$$, where $$$p_i$$$ is the parent of vertex $$$i$$$; for vertices corresponding to strings from $$$S$$$, $$$dp$$$ values should be updated with the time required to autocomplete some of the parents to the current vertex.
To do these updates, let's calculate the answers for all strings in lexicographical order. We will run DFS on the trie and maintain a segment tree on the path from the root to the current vertex. In the segment tree, we will store the values of $$$dp_i + cost_i$$$, where $$$cost_i$$$ is the number of seconds required to autocomplete from $$$i$$$ to the current vertex. Obviously, if we are currently in a vertex representing a word from $$$S$$$, then we have to find the minimum in this segment tree — and that will be the cost to get to current vertex using autocompletion.
How to maintain $$$dp_i + cost_i$$$? Recall that we are running DFS on trie in lexicographical order. When we want to compute the answer for the first string, the value of $$$cost_i$$$ for all vertices is $$$1$$$, since our string will be the first in all autocompletion lists. And here's a trick to maintain these values for other strings: whenever we compute the answer for some string, add $$$1$$$ on the whole tree. For vertices that are ancestors of both current string and some next string, this $$$+1$$$ will stay and increase the cost to autocomplete the next string accordingly; but for vertices which are not on the path to some next string, the values of $$$dp_i + cost_i$$$ will be already deleted from the segment tree and replaced by new values — so this addition does not affect them.
Overall, this works in $$$O(n \log n)$$$, but it can be written in $$$O(n)$$$ with a vector instead of a segment tree (since all additions and minimum queries affect the whole structure).