Autocompletion (Codeforces 1312G)
Tags: DP, dfs and similar

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

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

Sample Inputs:
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

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

Sample Outputs:
2 4 1 3 3

1 2 2 4 4

Solution (Python):
import io
import os
DEBUG = False

def dfs(trie, root, preorder=None, postorder=None):
    stack = [root]
    seen = set()
    while stack:
        nodeId = stack.pop()
        if nodeId not in seen:
            if preorder:
                preorder(nodeId)
            stack.append(nodeId)
            seen.add(nodeId)
            for (c, childId) in reversed(trie[nodeId]):
                stack.append(childId)
        elif postorder:
            postorder(nodeId)

def solve(N, PC, K, A):
    ROOT = 0
    trie = {ROOT: []}
    parent = {}
    for (i, (p, c)) in enumerate(PC, 1):
        trie[p].append((c, i))
        assert i not in trie
        trie[i] = []
        parent[i] = p
    terminal = set(A)
    for children in trie.values():
        children.sort()
    offset = 0
    ancestor = []
    dist = {}

    def getDistPre(nodeId):
        nonlocal offset
        best = None
        if nodeId != 0:
            assert nodeId in parent
            best = 1 + dist[parent[nodeId]]
            if nodeId in terminal:
                best = min(best, ancestor[-1] + offset + 1)
            ancestor.append(min(ancestor[-1], best - offset))
            if nodeId in terminal:
                offset += 1
        else:
            best = 0
            ancestor.append(0)
        dist[nodeId] = best

    def getDistPost(nodeId):
        ancestor.pop()
    dfs(trie, ROOT, preorder=getDistPre, postorder=getDistPost)
    if DEBUG:

        def printNode(nodeId, word):
            return str(nodeId) + '\t' + word + ('$' if nodeId in terminal else '') + '\t' + 'dist: ' + str(dist[nodeId])
            return str(nodeId) + '\t' + word + ('$' if nodeId in terminal else '')

        def printGraph(nodeId, path):
            W = 8
            depth = len(path)
            for (ch, childId) in trie[nodeId]:
                path.append(ch)
                print((' ' * (W * depth) + '└' + ch.center(W - 1, '─') + str(childId) + ('$' if childId in terminal else '')).ljust(50) + printNode(childId, ''.join(path)))
                printGraph(childId, path)
                path.pop()
        printGraph(ROOT, [])
    out = []
    for a in A:
        out.append(str(dist[a]))
    return ' '.join(out)
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    (N,) = list(map(int, input().split()))
    PC = []
    for i in range(N):
        (p, c) = input().decode().split()
        PC.append((int(p), str(c)))
    (K,) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = solve(N, PC, K, A)
    print(ans)

Solution (Python):
import io
import os
DEBUG = False

def dfs(trie, root, preorder=None, postorder=None):
    stack = [root]
    seen = set()
    while stack:
        nodeId = stack.pop()
        if nodeId not in seen:
            if preorder:
                preorder(nodeId)
            stack.append(nodeId)
            seen.add(nodeId)
            for (c, childId) in reversed(trie[nodeId]):
                stack.append(childId)
        elif postorder:
            postorder(nodeId)

def solve(N, PC, K, A):
    ROOT = 0
    trie = {ROOT: []}
    parent = {}
    for (i, (p, c)) in enumerate(PC, 1):
        trie[p].append((c, i))
        assert i not in trie
        trie[i] = []
        parent[i] = p
    terminal = set(A)
    for children in trie.values():
        children.sort()
    offset = 0
    ancestor = []
    dist = {}

    def getDistPre(nodeId):
        nonlocal offset
        if nodeId == 0:
            dist[nodeId] = 0
            ancestor.append((0, nodeId, offset))
        else:
            assert nodeId in parent
            best = 1 + dist[parent[nodeId]]
            if nodeId in terminal:
                (sortKey, ancestorId, oldOffset) = ancestor[-1]
                assert sortKey + offset + 1 == dist[ancestorId] + (offset - oldOffset) + 1
                best = min(best, dist[ancestorId] + (offset - oldOffset) + 1)
            ancestor.append(min(ancestor[-1], (best - offset, nodeId, offset)))
            dist[nodeId] = best
            if nodeId in terminal:
                offset += 1

    def getDistPost(nodeId):
        ancestor.pop()
    dfs(trie, ROOT, preorder=getDistPre, postorder=getDistPost)
    if DEBUG:

        def printNode(nodeId, word):
            return str(nodeId) + '\t' + word + ('$' if nodeId in terminal else '') + '\t' + 'dist: ' + str(dist[nodeId])
            return str(nodeId) + '\t' + word + ('$' if nodeId in terminal else '')

        def printGraph(nodeId, path):
            W = 8
            depth = len(path)
            for (ch, childId) in trie[nodeId]:
                path.append(ch)
                print((' ' * (W * depth) + '└' + ch.center(W - 1, '─') + str(childId) + ('$' if childId in terminal else '')).ljust(50) + printNode(childId, ''.join(path)))
                printGraph(childId, path)
                path.pop()
        printGraph(ROOT, [])
    out = []
    for a in A:
        out.append(str(dist[a]))
    return ' '.join(out)
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    (N,) = list(map(int, input().split()))
    PC = []
    for i in range(N):
        (p, c) = input().decode().split()
        PC.append((int(p), str(c)))
    (K,) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = solve(N, PC, K, A)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
T = [input().split() for i in range(n)]
k = int(input())
S = list(map(int, input().split()))
SETS = set(S)
E = [[] for i in range(n + 1)]
P = [-1] * (n + 1)
for i in range(n):
    (p, s) = T[i]
    p = int(p)
    E[p].append((s, i + 1))
    P[i + 1] = p
for i in range(n + 1):
    E[i].sort(reverse=True)
ELI = [0] * (n + 1)
DEPTH = [0] * (n + 1)
ELIMIN = [0] * (n + 1)
ANS = [0] * (n + 1)
Q = [0]
USED = [0] * (n + 1)
count = 0
while Q:
    x = Q.pop()
    USED[x] = 1
    if x in SETS:
        count += 1
    if x in SETS:
        ANS[x] = min(DEPTH[x], count + ELIMIN[P[x]], ANS[P[x]] + 1)
        ELI[x] = ANS[x] - count + 1
    else:
        ANS[x] = min(DEPTH[x], ANS[P[x]] + 1)
        ELI[x] = ANS[x] - count
    ELIMIN[x] = min(ELI[x], ELIMIN[P[x]])
    for (s, to) in E[x]:
        if USED[to] == 1:
            continue
        Q.append(to)
        DEPTH[to] = DEPTH[x] + 1
print(*[ANS[s] for s in S])