P5353 Suffix Sorting on a Tree

Given a tree rooted at $1$ with $n$ nodes, it is guaranteed that for every node from $2$ to $n$, the index of its parent is smaller than its own index. Each node has a character. The string represented by a node is defined as the string formed by concatenating all characters on the simple path from the current node up to the root. Please sort these strings in lexicographical order. In particular, if the strings represented by two nodes are exactly the same, their order is determined by the order of their parents: the one whose parent has a larger rank is considered larger. If they are still the same, then their order is determined by their node indices: the one with the larger index is considered larger.

The first line contains a positive integer $n$. The second line contains $n - 1$ integers $f_{2 \dots n}$, where $f_i$ denotes the parent of node $i$. The third line contains a string $s$ of length $n$ consisting of **lowercase letters**, where $s_i$ is the character on node $i$.

Output one line with $n$ positive integers. The $i$-th integer denotes the node index that represents the **string ranked $i$-th**.

For $20\%$ of the testdata, $n \le 10 ^ 3$. For $50\%$ of the testdata, $n \le 10 ^ 5$. For $100\%$ of the testdata, $1 \le n \le 5 \times 10 ^ 5$. Translated by ChatGPT 5