P9399 "DBOI" Round 1 Life Is Like a Tree

> _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](https://www.luogu.com.cn/problem/P6773), everyone’s life is a tree. It always grows in endless randomness and fate: some branches flourish, while some inevitably wither.

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

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.

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

### 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:  | Subtask | $n \le$ | $m \le$ | Special Properties | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | Subtask 1 | $5000$ | $5000$ | None | $10$ | | Subtask 2 | $10^5$ | $5\times{10}^4$ | A & B | $30$ | | Subtask 3 | $10^5$ | $5\times{10}^4$ | B | $30$ | | Subtask 4 | $10^5$ | $5 \times {10}^4$ | None | $20$ | | Subtask 5 | $10^5$ | $10^5$ | None | $10$ | 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