Problem Description

Given a rooted tree with $n$ nodes, rooted at $1$. The $i$-th node has a node weight $a_i$.

Define the function $f(u,v)$ as the median of the multiset of node weights of all nodes on the path from $u$ to $v$.

Note that the definition of median in this problem is slightly different from the standard mathematical one: for a sequence of length $t$, its median is defined as the $\left\lceil\frac{t+1}2\right\rceil$-th smallest number in the sequence.

Define the function $\text{cover}(x_1,y_1,x_2,y_2)$ to indicate whether the path from $x_1$ to $y_1$ completely covers the path from $x_2$ to $y_2$. If it completely covers, then $\text{cover}(x_1,y_1,x_2,y_2)=1$; otherwise, $\text{cover}(x_1,y_1,x_2,y_2)=0$.

You need to process $q$ operations in order, in the following formats:

1 u: an update operation, where you need to XOR the weight of node $u$ with $1$;

2 u v: a query, where you need to compute $\max\limits_{1\le i\le n,1\le j\le n}\{\text{cover}(i,j,u,v)f(i,j)\}$.

For the second type of operation, it is guaranteed that in every query, $u$ is not an ancestor of $v$ and $v$ is not an ancestor of $u$, and $u \neq v$.

For each operation of the second type, output the corresponding value.

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of nodes in the tree and the number of queries.

The second line contains $n$ integers, where the $i$-th number is the node weight $a_i$.

The next $n-1$ lines each contain two integers $x,y$, describing an edge connecting $x$ and $y$.

The next $q$ lines each start with an integer $opt$, indicating whether this is an update or a query. If $opt=1$, this is an update, and it is followed by an integer $u$. If $opt=2$, this is a query, and it is followed by two integers $u,v$. The specific meanings are described in the [Description].

Output Format

For each query, output one line containing the answer.

8 3
4 2 3 4 2 1 4 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
2 4 8
1 3 
2 2 3

3
4

Hint

[Sample Explanation]

The first operation is a query. Clearly, only $(i=4,j=8)$ satisfies $\text{cover}(i,j,u,v)=1$. In this case, $f(i,j)=3$.

The second operation is an update. The node weight of node $3$ is changed to $2$.

The third operation is a query. When $i=4,j=3$, $\text{cover}(i,j,u,v)=1$ and $f(i,j)=4$. It is not hard to see that for all other node pairs $(i,j)$ satisfying $\text{cover}(i,j,u,v)=1$, none has $f(i,j)>4$.

[Constraints]

• Subtask 1 (8 pts): $n,q\le50$;
• Subtask 2 (12 pts): $n,q\le2\times10^3$;
• Subtask 3 (16 pts): $n,q\le4\times10^4$;
• Subtask 4 (10 pts): the shape of the tree is guaranteed to be generated randomly;
• Subtask 5 (12 pts): it is guaranteed that there are no type $1$ operations;
• Subtask 6 (12 pts): it is guaranteed that in each query, both $u$ and $v$ are leaf nodes;
• Subtask 7 (30 pts): no special restrictions.

The random method in Subtask 4 is: randomly generate a permutation $p$. For $i\in[2,n]$, connect $p_i$ to a uniformly random node among $p_1,p_2,...,p_{i-1}$.

For $100\%$ of the testdata, $1\le n,q,a_i \le 10^5$. It is guaranteed that every query satisfies that $u$ is not an ancestor of $v$ and $v$ is not an ancestor of $u$, and $u \neq v$.

Translated by ChatGPT 5