题目描述

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

解题思路

倍增+dfs
题目表明v一定在u去网1的最短路径上，所以朴素的思想就是把u一个个向上提，再去判断到达的每一个城市，需不需要购买。
这种算法的极端情况，斜树+叶子与根，时间复杂度达到了O(nq)，后面给卡掉了。
能不能优化这个算法，我们知道，从u向上找v，这个好像和LCA比较相似，那我们能不能根据倍增的思路，去把寻找这个过程优化呢。
当然是有的，倍增的强大思路就来了，首先我们选择离线全部的查询，把每一个起点当作是新节点的父节点，终点另外一个数组记录，自己手上珠宝权值也是另外记录记作新点的点权。那么我们可以假设：
dp[i][j]是从i节点开始，购买 次珠宝到达的节点
那么根据倍增的递推式可以得到dp[i][j]=dp[dp[i][j-1]][j-1]
因为dfs的原因，父节点都已经处理完毕，可以更新子节点部分。
最后查询的时候，从起点出发，如果购买一定次数到达的节点深度小于终点，说明可以在去v的路上购买这些次数的珠宝。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43628435&returnHomeType=1&uid=919749006

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 2e5 + 7;
vector<int> e[N];
//             价值    深度    终点
int dp[N][20], a[N], dep[N], to[N];
// dp[i][j] 记录从i出发购买2^j次珠宝到达的节点

void dfs(int x, int fa) {
    int tmp = fa; //记录初始父亲，防止死循环
    dep[x] = dep[fa] + 1;
    for (int i = 19; i >= 0; --i)
        if (dp[fa][i] && a[dp[fa][i]] <= a[x])  //从父节点出发，向上寻找最远的大于a[x]的节点
            fa = dp[fa][i];
    if (a[fa] > a[x])    dp[x][0] = fa; //如果fa的值仍然大于a[x]，那么购买2^0定义为fa
    else    dp[x][0] = dp[fa][0];     // 否则就把从fa买1次的终点定义给x买一次的终点
    for (int i = 1; i < 20; ++i)
        dp[x][i] = dp[dp[x][i - 1]][i - 1];
    for (auto it : e[x])
        if (it != tmp)    dfs(it, x);
}

int main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)    a[i] = read();
    for (int i = 1; i < n; ++i) {
        int x = read(), y = read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i = n + 1; i <= n + m; ++i) {
        int x = read(), y = read(), z = read();
        e[x].push_back(i);
        e[i].push_back(x);
        to[i] = y;    a[i] = z;
    }
    dfs(1, 0);
    for (int i = n + 1; i <= n + m; ++i) {
        ll cnt = 0, tmp = i;
        for (int j = 19; j >= 0; --j)
            if (dep[dp[tmp][j]] >= dep[to[i]]) { //再去1的路上 有一个可以买2^j次珠宝的路径
                cnt += 1 << j; //购买次数
                tmp = dp[tmp][j];
            }
        printf("%lld\n", cnt);
    }
    return  0;
}