Colorful Tree Queries

You are given a tree with n nodes, where each node has a color. The tree is connected by n-1 edges. You are also given m queries. Each query contains three integers l, r, x.

For each query, consider the subgraph induced by all nodes whose indices are in the range [l, r]. In this subgraph, find the connected component that contains the node x (if it exists) and output the number of distinct colors in that component. If node x is not present in the induced subgraph, output 0.

Note: The queries are independent; that is, each query is applied on the original tree.

Formally:

For each query, if we let \(G[l, r]\) be the subgraph induced by nodes labeled in \([l, r]\) and \(C(x)\) be the connected component in \(G[l, r]\) that contains node \(x\), then you must compute

[ \text{answer} = #{\text{colors in } C(x)},, ]

and if \(x\notin [l, r]\), then the answer is 0.

inputFormat

Input Format:

• The first line contains two integers n and m, representing the number of nodes in the tree and the number of queries respectively.
• The second line contains n integers, where the \(i\)-th integer represents the color of node \(i\>.
• The next n-1 lines each contain two integers \(u\) and \(v\) denoting an undirected edge connecting nodes \(u\) and \(v\).
• The following m lines each contain three integers l r x representing a single query.

Note: Nodes are numbered from 1 to n.

outputFormat

Output Format:

• For each query, output a single integer on a new line—the number of distinct colors in the connected component containing node x in the subgraph induced by nodes in the range \([l, r]\). If node x is not present in the subgraph, print 0.

sample

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

3
2
1