Tree Connected Component Updates and Queries

You are given a tree with \(n\) nodes, where the \(i\)th node has an initial weight \(a_i\). In the tree, two nodes are considered connected if there is a path between them such that every two consecutive nodes on the path have the same weight.

For any node \(x\), define its maximal same-color connected component as the maximal set \(S\) that satisfies:

[ \begin{aligned} &x\in S,\ &\text{and for any } i,j\in S, \text{ there exists a sequence of nodes } p_1,p_2,\ldots,p_t \text{ with } p_1=i, p_t=j,\ &\quad\quad\text{such that for every } k\in{1,2,\ldots,t-1}, p_k \text{ and } p_{k+1} \text{ are adjacent in the tree and } a_{p_k}=a_{p_{k+1]}}. \end{aligned} ]

You need to perform \(m\) operations. There are two types of operations:

• 1 x y: For the node \(x\), update the weight of every node in its current maximal same-color connected component to \(y\). Note that the component is determined based on the weights before the update.
• 2 x: For the node \(x\), output the size of its current maximal same-color connected component.

Input Format: The input begins with two integers \(n\) and \(m\). The second line contains \(n\) integers, where the \(i\)th integer is \(a_i\). Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), indicating an edge between nodes \(u\) and \(v\). Finally, the next \(m\) lines each contain an operation in one of the two formats described above.

Output Format: For each query of type 2 x, output a single integer representing the size of the maximal same-color connected component of node \(x\) on a separate line.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and the number of operations).
The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial weights of the nodes.
The next \(n-1\) lines each contain two integers \(u\) and \(v\), indicating an edge between node \(u\) and node \(v\).
The following \(m\) lines each contain an operation in one of the following two formats:
1 x y to update, or 2 x to query.

outputFormat

For each query operation (type 2 x), output a single line containing the size of the connected component (maximal same-color connected component) that node \(x\) belongs to.

sample

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

1
5
5