题目描述

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

题解

注意题目里所说的‘**保证 v 在 u 前往首都的最短路径上’这就说明u，v,根，在一条链上。
那么我们就可以令dp[i][j]表示从i节点开始购入了2^j次所到达的点，转移方程为：
dp[i][j]=dp[dp[i][j-1]][j-1]。
在考虑怎么求dp[i][0]?
当i的父亲的珠宝>i的时dp[i][0]=fa，否则可以利用父亲的dp数组类似求lca那样得到dp[i][0].
考虑题中还有一个额外的C的限制，我们可以把c当作u的子节点，离线预处理即可。题目思路还是比较清晰的。注意几个细节吧

1.数组开两倍(新加了q个点
2.在求倍增求dp[i][0]时，要注意不能到达0节点，或者把0节点的价值设计为无穷

#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 2e5 + 6;
const LL inf = 0x3f3f3f3f;
//const int mod = 998244353;
//LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}

//head
int n,q,u[maxn],v[maxn],a[maxn],dp[maxn][50],dep[maxn];
VI G[maxn];

void dfs(int u,int fa){
    if(fa!=-1){
        if(a[u]<a[fa]) dp[u][0]=fa;
        else {
            int c=fa;
            for(int i=30;i>=0;i--){
                if(a[dp[c][i]]<a[u]&&dp[c][i]) {
                    c=dp[c][i];
                }
            }
            dp[u][0]=dp[c][0];
        }
        dep[u]=dep[fa]+1;
    }
    else dep[u]=1;

    for(int i=1;i<=30;i++){
        dp[u][i]=dp[dp[u][i-1]][i-1];
    }
    for(int i:G[u]){
        if(i==fa) continue;
        dfs(i,u);
    }
}

int main(){
    a[0]=inf;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,u,v;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&u[i],&v[i],&a[i+n]);

        G[i+n].pb(u[i]);
        G[u[i]].pb(i+n);
        u[i]=i+n;
    }
    dfs(1,-1);
    for(int i=1;i<=q;i++){
        int ans=0;
        for(int j=30;j>=0;j--){
            if(dep[dp[u[i]][j]]>=dep[v[i]]){
                ans+=(1<<j);
                u[i]=dp[u[i]][j];
            }
        }
        printf("%d\n",ans);
    }
}