#6192. 「美团 CodeM 复赛」城市网络
内存限制：64 MiB 时间限制：500 ms 标准输入输出
题目描述
有一个树状的城市网络（即 nnn 个城市由 n−1n-1n−1 条道路连接的连通图），首都为 111 号城市，每个城市售卖价值为 aia_iai 的珠宝。
你是一个珠宝商，现在安排有 qqq 次行程，每次行程为从 uuu 号城市前往 vvv 号城市（走最短路径），保证 vvv 在 uuu 前往首都的最短路径上。
在每次行程开始时，你手上有价值为 ccc 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 uuu 和 vvv），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。
输入格式
第一行，两个正整数 n,qn , qn,q。
第二行，nnn 个正整数 aia_iai 描述每个城市售卖的珠宝的价值。
接下来 n−1n-1n−1 行，每行描述一条道路 x,yx , yx,y (1≤x,y≤n1 leq x , y leq n1≤x,y≤n)，表示有一条连接 xxx 和 yyy 的道路。
接下来 qqq 行，每行描述一次行程 u,v,cu , v , cu,v,c (1≤u,v≤n1 leq u , v leq n1≤u,v≤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%100 \%100% 的数据，保证 2≤n≤105,1≤q≤1052 leq n leq 10^5 , 1 leq q leq 10^52≤n≤105,1≤q≤105 , 1≤ai≤1051 leq a_i leq 10^51≤ai≤105 , 1≤c≤1051 leq c leq 10^51≤c≤105。