Migrated from Lutece 2946 冉冉的树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag:点分治+cdq分治
冉冉最近痴迷于树上问题。
这一天，冉冉又在研究新的问题： 给定一个$n$个节点的树，点编号从$1$到$n$，每个点有权值$a_i$。现在有$m$次询问，每次询问给定参数$l,r,x$，询问如果只保留树上编号在$[l,r]$的点，其余的点和与它们相关的边全部删除，求编号为$x$的点所在连通块里有多少个点满足其权值小于点$x$的权值。所有询问相互独立，即某次询问时删除的点和边仅在本次询问时被删除。 不过由于冉冉马上要去和女朋友约会了，所以他把这个问题抛给了你这只单身狗。

Input

输入第一行包含两个整数$n$和$m$，表示树的大小和询问次数。
输入第二行包含$n$个整数$a_i$，第$i$个整数$a_i$表示编号为$i$的点的权值。
接下来$n-1$行，每行包含两个整数$u$和$v$，表示编号为$u$的点和编号为$v$的点之间存在一条边。
接下来$m$行，每行包含三个整数$l,r,x$，表示询问如果只保留树上编号在$[l,r]$的点，则编号为$x$的点所在连通块里有多少个点满足其权值小于等于点$x$的权值。

Output

输出包含$m$行。对于每一次询问，输出一行一个整数，表示本次询问的答案。

Samples

7 3 
5 2 1 1 3 1 4
1 2
1 3
2 4
2 5
3 6
6 7
1 7 5
2 7 5
3 7 5

5
3
1

Constraints

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

Resources

2023 UESTC ICPC Training for Data Structures