Background

Always this cool, always, always this cool
Like an adventurer, keep exploring the road to the mountaintop
— "Hustle"

Zhang Junhao looked out of the window. Zhu Zhixin walked over and sat beside him, folded a paper plane, and threw it out. He told Zhang Junhao to carry expectations for the future, move forward, and do not look back.

Just as described in Destiny, everyone’s life is a tree. It always grows in endless randomness and fate: some branches flourish, while some inevitably wither.

Problem Description

Zhu Zhixin obtained Zhang Junhao’s life tree using magic.

This is a tree with $n$ nodes, and node $i$ has weight $w_i$.

Zhu Zhixin wants to observe $m$ moments of Zhang Junhao’s life:

Let the number of nodes on the current life tree be $s$.

1. Input four integers $u_1, v_1, u_2, v_2$. Let the array formed by the nodes on the simple path $u_1 \to v_1$ in order be $a$, and the array formed by the nodes on the simple path $u_2 \to v_2$ in order be $b$. Zhu Zhixin believes the similarity of these two segments of life is $LRP(a,b)$, and wants you to compute it. It is guaranteed that $1 \leq u_1, v_1, u_2, v_2 \leq s$.

2. Input two integers $u, w'$. Zhu Zhixin observed another possible future of Zhang Junhao, so you need to create a new node with weight $w'$, numbered $s + 1$, and add an undirected edge $(s + 1, u)$, where $u \leq s$. Clearly, after that, $s \leftarrow s + 1$.

For two arrays $a, b$, define their similarity $LRP(a,b)$ as the maximum $i$ such that $i \leq \min\{|a|, |b|\}$ and for all $1 \leq j \leq i$, we have $b_j = a_j + j$. Here $|a|$ denotes the length of array $a$. In particular, if no such $i$ exists, then $LRP(a,b) = 0$.

Input Format

The first line contains three positive integers $n, m, idx$, representing the number of nodes in the tree, the number of operations, and the Subtask index of this test point. For the samples, $idx = 0$.

The next line contains $n$ integers. The $i$-th integer is $w_i$, the weight of node $i$.

The next $n - 1$ lines each contain two positive integers $u_i, v_i$, indicating an undirected edge $(u_i, v_i)$.

The next $m$ lines each describe one operation. The first integer in each line is $opt$, and the following integers specify the operation. When $opt = 1$, it is operation 1; when $opt = 2$, it is operation 2.

Output Format

For each operation 1, output one line containing the queried $LRP(a, b)$.

9 3 0
7 3 2 4 6 5 5 3 7
1 2
2 3
2 4
4 5
4 6
1 7
7 8
7 9
2 9 10
1 3 5 8 10
1 3 6 8 10

4
3

13 5 0
15 12 9 11 5 6 16 14 15 10 12 1 2
7 8
5 6
2 9
1 2
4 5
8 2
9 10
2 3
10 11
3 4
3 13
3 12
1 1 6 7 11
1 12 12 13 13
2 1 10
2 2 11
1 14 14 15 15

6
1
1

Hint

Sample Explanation

For sample 1, after the first operation, $w_{10} = 10$, and the tree is shown in the figure:

• For the second operation, the first path is $3 \to 2 \to 4 \to 5$, so $a = \{2, 3, 4, 6\}$. The second path is $8 \to 7 \to 9 \to 10$, so $b = \{3, 5, 7, 10\}$. Since $3 = 2 + 1$, $5 = 3 + 2$, $7 = 4 + 3$, $10 = 6 + 4$, the answer is $4$.
• For the third operation, $a = \{2, 3, 4, 5\}$, $b = \{3, 5, 7, 10\}$. Since $3 = 2 + 1$, $5 = 3 + 2$, $7 = 4 + 3$, but $10 \ne 5 + 4$, the answer is $3$.

For sample 2, the initial tree is shown in the figure:

Special Property A: $v_i = u_i + 1$.

Special Property B: It is guaranteed that there is no operation 2.

Constraints: For $100\%$ of the data, $1 \leq n, m \leq 10^5$, $1 \leq w_i, w' \leq 10^6$, $1 \leq u_i, v_i \leq n$.

Translated by ChatGPT 5