P7357 “PMOI-1” Median.

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.

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

For each query, output one line containing the answer.

[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