Solution

求树上的简单路径很明显是LCA的题目，那么：
直接预处理父节点数组和深度数组直接暴力把 u 和 v 往上提 ？那就错了。
其实题目里有保证 v 在 u 前往首都的最短路径上，所以只需要直接把 u 向上遍历就可以了。
而珠宝购入的前提是当前城市的珠宝严格大于手中的所有珠宝，所以只需要再用两个变量维护珠宝的最大值和购入次数即可。
显然在数据小的情况下以上暴力可以AC，但是数据量一大超时就必不可免了。
可以优化的过程便是 u 找 v 这个过程，那么就要用到本文第一句话的LCA。
由于出发节点的价值大的时候也会购入，所以可以处理询问的时候可以把每组询问离线，出发点作为新节点的父亲，带着的珠宝价值作为新点的点权，目标点用新的数组存终点。
设 f[u][i] 为从u节点出发要购入 2^i 次珠宝第一次到达的城市，
由于是从根节点开始dfs，所以父节点都是处理好的，
那么倍增的递推式很明显： f[u][i]= f[ f[u][i-1] ][i-1];
那么最后只要倍增使每组询问的两个点深度相同即可，步数为 f[u][i] 的 2^i 。

Code

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define inf 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define ins insert
#define eps 1e-8
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("YES") ;}void put2(){ puts("NO") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const ull base=2333; const ull pp=19260811; const ull ppp=999998639;

const int manx=2e5+5;
const int mo=998244353;

vector<ll>g[manx];
ll f[manx][25],a[manx],to[manx],d[manx];

void dfs(ll u,ll pre){
    ll father=pre;
    d[u]=d[pre]+1;
    for(int i=19;i>=0;i--)
        if(a[ f[pre][i] ]<=a[u]&&f[pre][i])
            pre=f[pre][i];
    if(a[pre]>a[u]) f[u][0]=pre;
    else f[u][0]=f[pre][0];
    for(int i=1;i<=19;i++)
        f[u][i]=f[ f[u][i-1] ][i-1];
    for(auto v : g[u]){
        if(v==father) continue;
        dfs(v,u);
    }
}

int main()
{
    ll n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<n;i++){
        ll u=read(),v=read();
        g[u].pb(v); g[v].pb(u);
    }
    for(int i=n+1;i<=n+m;i++){
        ll u=read(),v=read(),w=read();
        g[u].pb(i); g[i].pb(u);
        to[i]=v;  a[i]=w;
    }
    dfs(1,0);
    for(int x=n+1;x<=n+m;x++){
        ll cnt=0,u=x;
        for(int i=19;i>=0;i--){
            if(d[ f[u][i] ]>=d[ to[x] ]){
                cnt+=(1<<i);
                u=f[u][i];
            }
        }
        printf("%lld\n",cnt);
    }
    return 0;
}