题意：
思路：
有一个关键信息就是v一定是u的祖先，也就是说从u向根节点跳的时候一定可以到达v
考虑用倍增处理，d p [ i ] [ j ]表示从i向根节点走并且购买了2 j件物品的位置
转移也是正常的转移d p [ i ] [ j ] = d p [ d p [ i ] [ j − 1 ] ] [ j − 1 ]
关键在于d p [ i ] [ 0 ]的确定，d p [ i ] [ 0 ]的含义就是i 向上走第一个大于a [ i ]的位置
如果a [ f a ] > a [ u ] 的话，那么d p [ u ] [ 0 ] = f a
不然，就从d p [ f a ] [ j ]进行倍增来找到d p [ u ] [ 0 ]
处理d p的过程用d f s实现，所以在遍历到u的时候，父节点f a的信息已经保留了。从f a向上跳，如果跳到某个点存在并且价值小于u，跳到这个点后再向上跳；价值大于u的话，说明正确位置在该点下面的点，缩小i继续跳。与正常的倍增一样，i也要从大到小枚举
对于查询，可以将每次询问都增加一个节点x到u，a [ x ] = c，这样方便处理。然后从x向v跳，每次从大到小枚举i，比较深度。由于每个数一定能拆成二进制数，所以一定可以跳到v每次的答案增加2 i
注意：要开两倍数组
代码：
const int maxn=2e5+7; vector<int>g[maxn]; int n,q,a[maxn],dep[maxn],pos[maxn],dp[maxn][25]; void dfs(int u,int fa){ dep[u]=dep[fa]+1; if(a[fa]>a[u]){ dp[u][0]=fa; } else{ int x=fa; for(int i=20;i>=0;i--) if(dp[x][i]&&a[dp[x][i]]<=a[u]){ //跳到这个点存在并且价值小于u，跳到这个点再向上跳；价值大于u的话，说明在该点下面的点，缩小i继续跳。 x=dp[x][i]; } dp[u][0]=dp[x][0]; } for(int i=1;i<=20;i++) dp[u][i]=dp[dp[u][i-1]][i-1]; for(auto t:g[u]){ if(t==fa) continue; dfs(t,u); } } int main(){ n=read,q=read; rep(i,1,n) a[i]=read; rep(i,1,n-1){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } rep(i,1,q){ int u=read,v=read,c=read; a[n+i]=c; g[n+i].push_back(u); g[u].push_back(n+i); pos[i]=v; } dfs(1,0); rep(i,1,q){ int u=n+i,v=pos[i],ans=0; for(int i=20;i>=0;i--) if(dep[dp[u][i]]>=dep[v]){ ans+=(1<<i);u=dp[u][i]; } printf("%d\n",ans); } return 0; }
