Solution

题目中有两个关键信息：

• 1号节点是根节点。
• 节点 在节点 到根节点的最短路径上。

由于是树形结构，所以从 到 一定是不断地将 ，也就是 是 的祖先。

于是可以先进行一次 预处理出每个节点的父节点，之后回答询问。只有当某个节点的珠宝比手中的都值钱是才会采购，所以一旦出现更有价值的，其他珠宝就没有比较的价值了。于是可以联系到单调栈。

具体来说，遇到比栈顶更有价值的珠宝时进行弹栈。如果弹完后栈中没有元素，则证明比当前的所有珠宝更有价值，就可以使答案加 ，再将此珠宝加入栈中即可。

时间复杂度： 。

Code

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+10;
int n,q,cnt,tp,ans,a[maxn],hd[maxn],fa[maxn],s[maxn];
struct edge{
    int t;
    int v;
}e[maxn<<1];
void add(int x,int y){
    cnt++;
    e[cnt].t=hd[x];
    e[cnt].v=y;
    hd[x]=cnt;
}
void Dfs(int u,int x){
    fa[u]=x;
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=x)
            Dfs(e[i].v,u);
}
int Query(int x,int y,int c){
    ans=tp=0;
    s[++tp]=0;
    a[0]=c;
    while(1){
        while(a[s[tp]]<a[x]&&tp>0)
            tp--;
        if(!tp){
            s[++tp]=x;
            ans++;
        }
        if(x==y)
            break;
        x=fa[x];
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int x,y,z;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    Dfs(1,1);
    for(int i=1;i<=q;i++){
        cin>>x>>y>>z;
        cout<<Query(x,y,z)<<endl;
    }
    return 0;
}

仔细考虑之后，发现这是一个找祖先的过程。联系倍增求 根据本道题的状态，可以设 为节点 之上的第 个采购珠宝的节点，则有

所以可以用一次 预处理出 数组，之后回答询问即可。由于询问的珠宝价格是独立的，所以可以新建一个节点并向询问中的 节点连边。

时间复杂度 。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=2e5+10;
int n,q,cnt,ans,a[maxn],hd[maxn],dep[maxn],f[20][maxn],b[maxn];
struct edge{
    int t;
    int v;
}e[maxn<<1];
void add(int x,int y){
    cnt++;
    e[cnt].t=hd[x];
    e[cnt].v=y;
    hd[x]=cnt;
}
void Dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    int x=fa;
    if(a[fa]>a[u])
        f[0][u]=fa;
    else{
        for(int i=19;i>=0;i--)
            if(f[i][fa]&&a[f[i][fa]]<=a[u])
                fa=f[i][fa];
        f[0][u]=f[0][fa];
    }
    for(int i=1;i<=19;i++)
        f[i][u]=f[i-1][f[i-1][u]];
    for(int i=hd[u];i!=0;i=e[i].t)
        if(e[i].v!=x)
            Dfs(e[i].v,u);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int x,y,z;
    for(int i=1;i<n;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=q;i++){
        cin>>x>>y>>z;
        add(n+i,x);
        add(x,n+i);
        a[n+i]=z;
        b[i]=y;
    }
    Dfs(1,0);
    for(int i=1;i<=q;i++){
        x=n+i,y=b[i],ans=0;
        for(int j=19;j>=0;j--)
            if(dep[f[j][x]]>=dep[y]){
                ans+=(1<<j);
                x=f[j][x];
            }
        cout<<ans<<endl;
    }
    return 0;
}