FiFo | RoAlgo Educational Contest #1 | Struct arbore{}

Task

The Powerpuff girls have encountered a computer science problem at the ONI. They are not familiar with struct arbore and that's why they ask for your help.
You are given $N$ nodes, each node having a specific lowercase letter.
For $Q$ queries, you have two types of queries you can receive:

• $1 \ x \ y$. Find the longest suffix of the $2$ nodes such that the words formed are identical. A word is defined as a chain of $len$ consecutive nodes. If we want to form a word from node $x$ to node $y$, $y$ must be the child of node $x$.
• $2 \ x \ ch$. Node $x$ will change its character value to $ch$.

The Powerpuff girls ask you to give them a code with the best possible complexity so that they get the gold medal.

Input data

On the first line is an integer, $N$, which is the number of nodes in the tree structure.
On the second line are $N$ letters, representing the letter for each node.
On the third line is $N-1$ containing the string $t$ , ($t_i$, $i=\overline{2,N}$), representing the father of node $i$ in the struct arbore.
On the fourth line is $Q$, representing the number of questions.
On the next $Q$ lines are information about the queries to perform.

Output data

The program will display the query results one line at a time, in the order they appear in the input.

Constraints and clarifications

• $N \leq 100 \ 000$;
• $Q \leq 100 \ 000$;
• The string will be indexed from $1$.

Comment

Due to the very large input data, we recommend using the following lines at the beginning of the main() function in the C++ program:

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Exemple 1

stdin

11
bfpfpprpbff
1 2 2 2 3 4 5 7 9 10
5
1 6 8
1 11 4
2 7 f
2 2 b
1 11 7

stdout

4
3
3

Explanation

The next picture shows our tree.
For the first question we observe that the longest suffix of the $6$ and $8$ nodes is formed by the sequence of nodes: $6 \rightarrow 3 \rightarrow 2 \rightarrow 1$, respectively: $8 \rightarrow 5 \rightarrow 2 \rightarrow 1$. We note that the node sequences $6 \rightarrow 3$ and $8 \rightarrow 5$ are also valid, but they do not have maximal length.
For the second question we observe that the longest suffix of nodes $11$ and $4$ is formed by the sequence of nodes: $11 \rightarrow 10 \rightarrow 9$, respectively: $4 \rightarrow 2 \rightarrow 1$. It can't be bigger, since the chain formed from node $4$ has reached the root.
Next we modify two nodes, so node $7$ goes from $r$ to $f$, and node $2$ from $f$ to $b$.
For the last question, the longest suffix will be $3$, consisting of nodes $11 \rightarrow 10 \rightarrow 9$, respectively: $7 \rightarrow 4 \rightarrow 2$.

Exemple 2

stdin

21
lncnfshipesgoragaorjj 
1 2 2 1 5 5 7 6 4 4 3 12 13 9 15 16 16 18 19 14
2
1 21 20
1 11 6

stdout

4
1