爱站程序员基地补题链接：Here
LCA 算法讲解：Here
考虑用 f[i][j] 表示从i往上走，能买珠宝的第 2^j 个点是哪个，显然，如果我们知道每个 $f[i][0]$的值， 那么 f[i][j]=f[f[i][j−1]][j−1] ( i 往上的第2 j−1 个点再往上 2j−1个点)。那么 f[i][0] 怎么求呢？肯定不能暴力，因为暴力最坏情况可能会让你每次都跑到根（构造一条链，从根到叶子价值递增）。这个其实也可也倍增着跳——如果 i 的父亲fa比i 大那自不必说，当i的父亲fa比i 小，那么我们可以看fa的父亲向上走 2^k（k从大到小枚举）个能买进的点的权值（即 f[fa][k]），如果这个点权限比 i 点权值小，说明还需要往上走，就跳到f[fa] [k]上并把跳跃的长度减少一半(如果还是刚刚的跳跃高度，从 $f[fa][k]$往上跳 2 ^k长度，实际上就是从fa跳 2^k+1 ，相当于就是跳到 $f[fa][k+1]$了）；如果 f[fa][k]这个点的权值比 i 大，说明跳多了，就只是把跳跃长度减少一半再看。注意我这里说的跳跃长度都是按照能买东西的点的个数计数，相当于我的f数组其实是对原树进行了重建，每个点往上走1步都的连向的它能到的第一个比他大的点（这样理解也许会容易很多——即我们对原树进行变形，每个点都连向它上方第一个能买东西的点，构成一个新的森林，于是问题就变成了，从u走到自己上方深度不小于dep[v]的点需要经过多少个点）。
有了这个值之后我们要求从 u 往上走到 v 经过了多少点，也可也倍增去求了——即从 u 出发尝试往上跳 2^k 高度，如果已经跳过 v 了，就减小 k，如果没有跳到 v 的上方，就先跳上去再减小 k。 注意，因为f数组存的能买东西的点，很有可能v根本不在这里面，所有跳的时候是通过判断深度来判断是否结束的。
这道题想了好久好久 最终还是参考清楚姐姐的思路才想明白 /(ㄒoㄒ)/~~
// Murabito-B 21/04/10#include <bits/stdc++.h>using namespace std;const int maxn = 2e5 + 10;typedef long long ll;vector<int> v[maxn];int a[maxn], f[maxn][20], dep[maxn], to[maxn];void dfs(int p, int fa) {int x = fa;for (int k = 19; k >= 0; k--)if (f[x][k] && a[f[x][k]] <= a[p]) x = f[x][k]; //如果x往上跳2^k步这个点存在，且这个点的权值比a[p]要小，就跳到这个点再往上跳if (a[x] > a[p]) f[p][0] = x; //判断比a[p]大的点到底是x还是x的上面那个点elsef[p][0] = f[x][0];//向上倍增的找到第一个比p权值大的点for (int i = 1; i < 20; i++) f[p][i] = f[f[p][i - 1]][i - 1];dep[p] = dep[fa] + 1; //维护高度int num = v[p].size();for (int i = 0; i < num; i++) {int to = v[p][i];if (to == fa) continue;dfs(to, p); //搜子树}}int main() {ios::sync_with_stdio(false), cin.tie(0);int n, q;cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;v[x].push_back(y);v[y].push_back(x);}for (int i = n + 1; i <= n + q; i++) {int x, y, c;cin >> x >> y >> c;v[i].push_back(x);v[x].push_back(i);a[i] = c;to[i - n] = y; //记录对应的终点}dfs(1, 0);for (int i = 1; i <= q; i++) {int ans = 0;int x = i + n; //i+n是第i个询问的起点for (int k = 19; k >= 0; k--) { //k从大到小枚举if (dep[f[x][k]] >= dep[to[i]]) { //如果跳完之后深度小于目标点深度就已经走过了，跳跃高度要减小ans += (1 << k); //点数加2^kx = f[x][k]; //向上跳2^k个点}}cout << ans << endl;}return 0;}
