题目链接 题意 有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。 现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝，每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的所有珠宝的最大值要优秀（价值更高，即严格大于），那么你就会选择购入。现在你想要对每一次行程，求出会进行多少次购买事件。 思路 保证v在u通往首都的最短路上，也就是说v是u,v的lca，从u到v，每经过一个珠宝价值比手上的珠宝价值大的城市，就要购买一次，并非是最长上升子序列，而是只要是比手上的珠宝价值大就要买，且买了后，手上的最大的珠宝价值变成了刚买的珠宝价值了。考虑倍增的思想，f[i][j]表示从i往上走，能买珠宝的第2^j个点是哪个，预处理处倍增数组，显然，只要求出f[i][0]，其他的就可以用f[i][j] = f[f[]i[j - 1][j - 1]求得（就像LCA求倍增数组的方法）。那么如何解f[i][0]，如果i的父亲节点x，满足val[i]<val[x]，则f[i][0] = x；如果val[i]>=val[x]，那么就要从父亲节点开始，去找第一个比val[i]大的节点，这里可以用倍增去求得，考虑f[x][k]，k从大到小枚举，这样可以快速缩短距离，如果val[f[x][k]]<=val[i]，则x=f[x][k]，从f[x][k]节点开始往上找；否则就找f[x][k-1]，判断val[f[x][k - 1]]是否大于val[i]，如此不断的趋近i上面的第一个比它大的值，最后找到的那个f[x][0]就是f[i][0]。 求解完倍增数组后，接下来就是处理询问了，题目问的是从u开始就有了价值为c的珠宝，那么我们新建一个节点与u点相连，价值为c，这样就可以直接求到这个点的倍增数组，通过该点的倍增数组来求解。从u到v的购买次数，也就是通过倍增数组从u往上跳，跳的总距离（从该点到父亲距离为1，如f[i][0]距离为1，f[i][1]距离为2）。因为v点不一定在u点的祖先节点上，题目保证v一定在u到根节点的路径上，所以v得深度一定比u小，所以用dep来判断是否应该停止向上跳。
#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 7; typedef long long ll; int n, q, a[maxn]; int head[maxn], to[maxn<<1], nex[maxn<<1], tot; void add(int x, int y) { to[tot] = y; nex[tot] = head[x]; head[x] = tot++; } int To[maxn], f[maxn][20], dep[maxn];//fa[u][i]:保存u结点往根方向第2^i个val大于它的结点 void dfs(int x, int fx) { dep[x] = dep[fx] + 1;//记录深度 if(a[x] < a[fx]) f[x][0] = fx;//若父节点p的val比u的val大，fa[u][0] = p else { int p = fx; for (int i = 19; i >= 0; i--) {//x逼近第一个比val[u]大的结点下方的结点 if(f[p][i] && a[f[p][i]] <= a[x]) p = f[p][i]; } f[x][0] = f[p][0];//得到第一个比val[u]的的祖先结点 } for (int i = 1; i <= 19; i++)//倍增数组，递推 f[x][i] = f[f[x][i - 1]][i - 1]; for (int i = head[x]; ~i; i = nex[i]) { int v = to[i]; if(v == fx) continue; dfs(v, x); } } int main() { memset(head, -1, sizeof(head)); scanf("%d%d", &n, &q); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1, x, y; i < n; i++) { scanf("%d%d", &x, &y); add(x, y); add(y, x); } for (int i = 1, x, y, z; i <= q; i++) { scanf("%d%d%d", &x, &y, &z); add(n + i, x);//存询问节点，方便用倍增数组计算 add(x, n + i); a[n + i] = z;//珠宝价值 To[i] = y;//目标节点 } dfs(1, 0); for (int i = 1; i <= q; i++) { int u = i + n, v = To[i], ans = 0; for (int j = 19; j >= 0; j--) { if(dep[f[u][j]] >= dep[v]) { u = f[u][j]; ans += (1<<j);//记录跳了多少个节点 } } printf("%d\n", ans); } return 0; }