P15750 [JAG 2024 Summer Camp #3] Coins on a Tree

There is an undirected tree with $N$ vertices numbered through $1$ to $N$. There is a coin on each vertex, and a lowercase English letter is written on each coin. You are playing a game to collect all the $N$ coins. You have a string $\mathbf{S}$ which is initially empty. You first visit the vertex $1$ and then repeatedly move to an adjacent vertex. You may visit each vertex any number of times. Whenever you visit a vertex where a coin is still put, you collect the coin and append the letter on the coin to the end of $\mathbf{S}$. When there is already no coin on the node you visit, you do nothing. Note that the coin on the vertex $1$ is collected first. After collecting all the $N$ coins, you have a string $\mathbf{S}$ of length $N$. What is the lexicographically smallest possible string that $\mathbf{S}$ can become?

The input consists of a single test case of the following format. $$\begin{aligned} &N \\ &p_2 \ p_3 \ \ldots \ p_N \\ &c_1c_2 \ldots c_N \end{aligned}$$ The first line consists of an integer $N$ ($2 \leq N \leq 200,000$), which is the number of vertices on the tree. The second line consists of $N - 1$ integers. Each $p_i$ ($2 \leq i \leq N$, $1 \leq p_i < i$) represents that the vertices $i$ and $p_i$ are adjacent. Note that $p_1$ is not given. The third line consists of a string of $N$ lowercase English letters. The $i$-th letter $c_i$ ($1 \leq i \leq N$) is the letter on the coin on the vertex $i$.

Print the lexicographically smallest possible string that $\mathbf{S}$ can become after collecting all the $N$ coins.