Description

You are given a tree with $n$ nodes. Each node has a color. There are $m$ queries.

Each query gives parameters $l\ r\ x$. You need to output:

Keep all nodes whose indices are in $[l,r]$ in the tree. In the connected component that contains $x$, output the number of distinct colors.

Each query is independent.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers representing the color of each node.

Then follow $n-1$ lines. Each line contains two integers $x$ and $y$, indicating there is an edge between $x$ and $y$.

Then follow $m$ lines. Each line contains three integers $l\ r\ x$, representing one query.

Output Format

For each query, output one line with one integer, the answer.

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

3
2
2
3

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: created_equal1, Data: nzhtl1477.

Constraints: For $100\%$ of the testdata, all numbers that appear are in $[1,10^5]$, and it is guaranteed that for each query $l \le x \le r$.

Translated by ChatGPT 5