#6192. 「美团 CodeM 复赛」城市网络

内存限制:64 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: sqc

题目描述

有一个树状的城市网络(即 n 个城市由 n-1 条道路连接的连通图),首都为 1 号城市,每个城市售卖价值为 a_i 的珠宝。

你是一个珠宝商,现在安排有 q 次行程,每次行程为从 u 号城市前往 v 号城市(走最短路径),保证 v u 前往首都的最短路径上。

在每次行程开始时,你手上有价值为 c 的珠宝(每次行程可能不同),并且每经过一个城市时(包括 u v ),假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀(价值更高,即严格大于),那么你就会选择购入。

现在你想要对每一次行程,求出会进行多少次购买事件。

输入格式

第一行,两个正整数 n , q

第二行, n 个正整数 a_i 描述每个城市售卖的珠宝的价值。

接下来 n-1 行,每行描述一条道路 x , y ( 1 \leq x , y \leq n ),表示有一条连接 x y 的道路。

接下来 q 行,每行描述一次行程 u , v , c ( 1 \leq u , v \leq n )。

输出格式

对于每次行程输出一行,为所购买次数。

样例

样例输入

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

样例输出

2
1
1
0

数据范围与提示

对于 100 \% 的数据,保证 2 \leq n \leq 10^5 , 1 \leq q \leq 10^5 , 1 \leq a_i \leq 10^5 , 1 \leq c \leq 10^5