Distinct weights on a tree path

You are given a tree with $N$ vertices. A tree is a connected undirected graph with no cycle. The vertices are numbered from 1 to $N$ and the edges are numbered from 1 to $N-1$. Every vertex carries one weight.

Write a program that answers the following query.

• u v: print how many different weight values appear among the vertices on the path from vertex $u$ to vertex $v$. The path includes both endpoints $u$ and $v$.

The first line contains the number of vertices $N$. ($2 \le N \le 100000$)

The second line contains the weights of vertices 1 through $N$ in order. Every weight is a positive integer no larger than $1000000$.

Each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ joined by edge $i$. The given edges always form a single tree.

The next line contains the number of queries $M$. ($1 \le M \le 100000$)

Each of the next $M$ lines contains one query in the form u v. Both $u$ and $v$ are between 1 and $N$, and queries where the two values are equal also occur.

Print the answer to each query on its own line, in the order the queries are given.