solution

倍增思想。
用st[i][j]表示从i号节点进行次购买所到达的节点。这个可以通过一遍dfs预处理出来。关键在于怎么找st[i][0],这个可以通过i号节点的父亲进行转移。具体参考代码。

然后考虑对于一次询问,找到u到根路径上比c大的深度最大的点。先跳到这个点然后不断向上跳,一直跳到v即可。
复杂度

code

/*
* @Author: wxyww
* @Date: 2020-04-02 19:59:55
* @Last Modified time: 2020-04-02 20:39:22
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010,logN = 20;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;
void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}

int fa[N],a[N],st[N][logN + 2],dep[N];
void dfs(int u,int father) {
    fa[u] = father;
    dep[u] = dep[father] + 1;
    if(a[father] > a[u]) st[u][0] = father;
    else {
        int x = father;
        for(int i = logN;i >= 0;--i)
            if(a[st[x][i]] <= a[u]) x = st[x][i];
        st[u][0] = st[x][0];
    }

    for(int i = 1;i <= logN;++i) 
        st[u][i] = st[st[u][i - 1]][i - 1];

    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == father) continue;
        dfs(v,u);
    }
}


int main() {
    int n = read(),Q = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }
    a[0] = 1e9;
    dfs(1,0);

    while(Q--) {
        int u = read(),v = read(),c = read();

        int x = u;
        if(a[x] <= c) {
            for(int i = logN;i >= 0;--i)
                if(a[st[x][i]] <= c) x = st[x][i];
            x = st[x][0];
        }
        int ans = 0;
        // if(dep[x] == dep[v]) ans = 1;
        // else 
        if(dep[x] >= dep[v]) {
            for(int i = logN;i >= 0;--i) {
                if(dep[st[x][i]] >= dep[v]) {
                    x = st[x][i];
                    ans += 1 << i;
                }
            }
            ans += 1;
        }
        printf("%d\n",ans);
    }

    return 0;
}