Dynamic Tree Subtree Weight Matching

You are given a tree with \(n\) nodes, each node having an integer weight. The tree is undirected and initially rooted at node \(1\). There are \(m\) operations. The operations are of two types:

• 1 x: Change the tree's root to node \(x\).
• 2 x y: For nodes \(x\) and \(y\), consider all pairs \((u,v)\) where \(u\) is in the subtree of \(x\) and \(v\) is in the subtree of \(y\) (both subtrees defined with respect to the current root). Count the number of pairs such that \(w(u)=w(v)\) (i.e. they have equal weights).

Note: The subtree of a node \(x\) (with respect to the current root \(T\)) is defined as all nodes \(v\) for which the unique simple path from \(T\) to \(v\) passes through \(x\). Equivalently, if \(x \neq T\), let \(p\) be the neighbor of \(x\) on the path from \(T\) to \(x\); then the subtree of \(x\) is the set of nodes reachable from \(x\) without going to \(p\).

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \leq n, m \leq \text{small constraints})\), the number of nodes and the number of operations.

The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) representing the weight of each node.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\).

The next \(m\) lines each describe an operation in one of the following formats:

• 1 x: Change the current root to \(x\).
• 2 x y: Query the number of pairs \((u,v)\) with \(u\) in the subtree of \(x\) and \(v\) in the subtree of \(y\) (with respect to the current root) such that \(w(u) = w(v)\).

outputFormat

For each query of the second type, output a single integer representing the answer on a new line.

sample

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

5
4
4