Path Cover Median Query on Tree

We are given a rooted tree with n nodes (rooted at 1) and an integer weight a_i associated with each node i. For any two nodes u and v in the tree, define the function $$ f(u,v) $$ as the median of the multiset of node weights along the unique simple path from u to v. Note that if the path contains t nodes, the median is defined as the $$\lceil \frac{t+1}{2} \rceil$$-th smallest number (1-indexed).

In addition, define the function $$ \text{cover}(x_1,y_1,x_2,y_2) $$ to be 1 if the path from x_1 to y_1 completely covers (i.e. contains every node of) the path from x_2 to y_2, and 0 otherwise.

You are to process q operations. There are two types of operations:

• Type 1: 1 u — Toggle the weight at node u by performing an XOR with 1 (i.e. set \(a_u = a_u \oplus 1\)).
• Type 2: 2 u v — Answer the query $$\max_{1\le i\le n,\,1\le j\le n} \{\text{cover}(i,j,u,v)\,f(i,j)\}.$$ It is guaranteed that in each type 2 query, u is not an ancestor of v, v is not an ancestor of u, and u \(\neq\) v.

For each type 2 query, output the corresponding maximum value on a separate line.

inputFormat

The first line contains two integers n and q, representing the number of nodes and the number of operations respectively. The second line contains n integers: (a_1, a_2, \ldots, a_n), where (a_i) is the weight of node i. The next n-1 lines each contain two integers u and v, indicating an edge between nodes u and v. The following q lines describe the operations in one of the following formats:

• 1 u: Toggle the weight of node u (i.e. \(a_u = a_u \oplus 1\)).
• 2 u v: Query the value of $$\max_{1\le i,j \le n} \{\text{cover}(i,j,u,v)\,f(i,j)\}.$$

It is guaranteed that for each query of type 2, u is not an ancestor of v and v is not an ancestor of u, with u \(\neq\) v.

outputFormat

For every operation of type 2, output a single integer representing the maximum value calculated, each on its own line.

sample

5 3
1 0 1 0 1
1 2
1 3
3 4
3 5
2 4 5
1 3
2 4 5

1
1

</p>