Query Distinct Values in Tree Paths

You are given a tree with N nodes. Each node is assigned an integer value. The tree is defined by N-1 edges connecting the nodes. You are also given Q queries. Each query consists of two nodes u and v. Your task is to determine the number of distinct node values along the simple path between nodes u and v.

Note: The tree is rooted at node 1. It is guaranteed that the input graph is a tree. Use efficient algorithms such as LCA (Lowest Common Ancestor) and tree traversal techniques.

The answer for each query should be computed as follows. Let \(P(u,v)\) be the set of nodes on the unique path from node \(u\) to node \(v\). You need to compute \(|\{ a_i : i \in P(u,v) \}|\), i.e. the count of unique values on that path.

inputFormat

The input is read from standard input (stdin) and has the following format:

N Q
v1 v2 ... vN
u1 v1
u2 v2
... (N-1 lines for edges)
q1_u q1_v
q2_u q2_v
... (Q lines for queries)

Where:

• N: the number of nodes in the tree.
• Q: the number of queries.
• v1, v2, ..., vN: the value assigned to each node (1-indexed).
• Each of the next N-1 lines contains two integers representing an edge of the tree.
• Each of the next Q lines contains two integers u and v representing a query.

outputFormat

For each query, output a single integer on a new line indicating the number of distinct values on the path from node u to node v.

## sample

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

4
3
3

</p>