题意：
思路：
对于每组查询，我们直接从$u$往上搜到$v$，复杂度$O(nq)$，显然不可取（不过这题开始的数据很弱，暴力就过了）
#include<bits/stdc++.h> using namespace std; int n,q; int a[100005]; int u,v,c; int par[100005]; vector<int> G[100005]; void dfs(int u,int v){ par[u]=v; for(auto i:G[u]){ if(i!=v) dfs(i,u); } } int cal(int u,int v,int c){ int num=0; while(u!=v){ if(a[u]>c){ c=a[u]; num++; } u=par[u]; } if(a[v]>c) num++; return num; } int main(){ cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; int t1,t2; for(int i=0;i<n-1;i++){ cin>>t1>>t2; G[t1].push_back(t2); G[t2].push_back(t1); } //preprocess dfs(1,0); while(q--){ cin>>u>>v>>c; cout<<cal(u,v,c)<<endl; } return 0; }#include<bits/stdc++.h> using namespace std; int n,q; int a[100005]; int u,v,c; int par[100005]; vector<int> G[100005]; void dfs(int u,int v){ par[u]=v; for(auto i:G[u]){ if(i!=v) dfs(i,u); } } int cal(int u,int v,int c){ int num=0; while(u!=v){ if(a[u]>c){ c=a[u]; num++; } u=par[u]; } if(a[v]>c) num++; return num; } int main(){ cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; int t1,t2; for(int i=0;i<n-1;i++){ cin>>t1>>t2; G[t1].push_back(t2); G[t2].push_back(t1); } //preprocess dfs(1,0); while(q--){ cin>>u>>v>>c; cout<<cal(u,v,c)<<endl; } return 0; }
离线查询
既然暴力超时的话，我们可以想到用性价比很高的树上倍增，有人说倍增的本质就是二进制拆分，想想也挺有道理的。
我们用$f[i][j]$表示从$i$往上走，能买到珠宝的第$2^j$的位置，这样很容易用倍增求出最后的答案。
显然，如果我们得出$f[i][0]$，那么其他关于节点$i$的值我可以很快通过递推得到
$$f[i][j] = f[f[i][j-1]][j-1]$$
那么对于某个节点$u$，怎么求$f[u][0]$呢？肯定不可能暴力从$u$节点遍历到根节点（假如退化成一条链复杂度会大大增加）
观察到，当$fa_u$的值大于$u$时，比 $u$大的第一个值，就是 $fa_u$；否则，就是比 $fa_u$大的第 $t$个值($t$为正整数)
而第二种情况我可以用倍增来求，说实话有点难理解为什么这样做就能求出来$f[u][0]$，不过官方给出一种理解方法：
我们的$f$数组其实是对原树进行了重建，每个点往上走$1$步都连向的它能到的第一个比他大的点
至于为什么可以用倍增找，我的一点小想法：
我们先来看暴力做法：从$fa_u$开始找，一定是先找到比$fa_u$大的节点，不满足的话继续找比当前值更大的节点，以此类推直到第$t$个点满足条件。而这个过程我们在对树进行重构后，明显可以使用倍增达到目的
之后具体过程和用倍增求$lca$一样，找到$f[u][0]$下方的点，最后往上跳一格就是$f[u][0]$
其实倍增的过程仔细想想，也有点二分的味道在里面
if(val[u]<val[fa]) f[u][0] = fa; else{ int x = fa; for (int i = 19; i >= 0; i--){ if (f[x][i] && val[u] >= val[f[x][i]]){ x = f[x][i]; } f[u][0] = f[x][0]; }
还有最后一个问题，题目说“每次行程开始时，你手上有价值为 $c$ 的珠宝”这个限制怎么办？很简单，在 $u $点的下方接一个权值为 $c$ 的点，然后从这个点开始往上走就可以了
问题就变成了，从$u$走到自己上方深度不小于$dep[v]$的点需要经过多少个点
关于倍增的一点看法：
通常我们要求 有指定要求的数，但是往往直接遍历求或者全部存储下来都不行通的，前者会超时后者会爆空间，所以一种折中的方法出现了——倍增。
我们只知道第$2^i$个点的情况，所以具体怎么知道哪个点是我们要找的呢？
通常这些点的信息都是有序的，比如说深度，那么我们可以想到以指定要求为限制进行二分
或者你从二进制的角度理解，假如第$t$个数就是我们要找的数，那么$t$可以拆分成二进制，既然我们知道每一位的信息，那么我们从高位往低位取，直到逼近我们要求的那个数
在线查询
并不是所有题目都会允许你离线查询，有的可能会要求强制在线，我们来看下在线的做法
Reference:
https://ac.nowcoder.com/discuss/395376?tdsourcetag=s_pctim_aiomsg
https://blog.nowcoder.net/n/970115deac7942b3a451a5f12630fb7c
https://blog.nowcoder.net/n/c6fd1e0583614363a2fc7b7f5fc6945b
https://blog.nowcoder.net/n/b6baecca0a36491c8d36671923477fff
https://blog.nowcoder.net/n/8528cf017ee148a1b98e994cd110335a
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43275876