Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

给你一棵 $n$ 个节点的树,每个节点有一种颜色,有 $m$ 次查询操作。

查询操作给定参数 $l ,r ,x$,需输出:

将树中编号在 $[l,r]$ 内的所有节点保留 $x$ 所在连通块中颜色种类数。

每次查询操作独立。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个数表示每个节点的颜色。

之后 $n-1$ 行,每行两个数 $x$ 和 $y$,表示 $x$ 和 $y$ 之间连有一条边。

之后 $m$ 行,每行三个数 $l,r,x$,表示一次查询操作。

输出格式

对每个查询操作,输出一行一个数表示答案。

输入输出样例

输入 #1

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

输出 #1

3
2
2
3

数据范围

$1 \le n,m \le 10^5 , l \le x \le r$