有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。
输入描述:
第一行，两个正整数 n , q (2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5)。
第二行，n 个正整数 a_i (1 ≤ a_i ≤ 10^5) 描述每个城市售卖的珠宝的价值。
接下来 n-1 行，每行描述一条道路 x , y (1 ≤ x,y ≤ n)，表示有一条连接 x 和 y 的道路。
接下来 q 行，每行描述一次行程 u , v , c (1 ≤ u,v ≤ n , 1 ≤ c ≤ 10^5)。


输出描述:
对于每次行程输出一行，为所购买次数。

输入例子1:
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

输出例子1:
2
1
1
0
解法：学的题解上的方法。很神奇啊，考虑离线处理，可以对每个询问，建出一个新点，作为叶子挂在起点下面。然后建一棵新树，对于每个点，求出它的祖先中，第一个比它权值大的，作为它在新树中 的父亲。
考虑在新树上处理询问，可以倍增找出需要跳多少点。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
vector <int> G[maxn];
int n, q, a[maxn], to[maxn], dep[maxn], fa[maxn][20];
void DFS(int x, int y)
{
    int pos = y;
    for(int i=19; i>=0; i--){
        if(fa[pos][i]&&a[fa[pos][i]]<=a[x]){
            pos = fa[pos][i];
        }
    }
    if(a[pos]>a[x]) fa[x][0] = y;
    else fa[x][0] = fa[pos][0];
    for(int i=1; fa[fa[x][i-1]][i-1]; i++) fa[x][i] = fa[fa[x][i-1]][i-1];
    dep[x] = dep[y]+1;
    for(int i=0; i<G[x].size(); i++){
        if(G[x][i] == y) continue;
        DFS(G[x][i], x);
    }
}
int main()
{
    scanf("%d %d", &n,&q);
    for(int i=1; i<=n; i++){
        scanf("%d", &a[i]);
    }
    for(int i=1; i<n; i++){
        int u, v;
        scanf("%d %d", &u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for(int i=1; i<=q; i++){
        int u,v,w;
        scanf("%d %d %d", &u,&v,&w);
        a[n+i] = w;
        to[n+i] = v;
        G[n+i].push_back(u);
        G[u].push_back(n+i);
    }
    DFS(1, 0);
    for(int i=n+1; i<=n+q; i++){
        int ans = 0, pos = i;
        for(int j=19; j>=0; j--){
            if(dep[fa[pos][j]] >= dep[to[i]]){
                ans += (1<<j);
                pos = fa[pos][j];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}