树上倍增问题

原图是这样的

当我们 输入 4 2 1 时 我们就是要找 从4 到 2 比 1 大的节点数，我们可以转换成这样的树，红色代表我们新加入的节点，显而易见，4号节点比 1大 ， 2号节点比 1大 答案为2

那我们就可以转换为把要查询的路径用这样的方式插入，实力太弱的我还是对数据结构掌握不好。~~
我们用f[i][j] 代表当前节点能够买 2^j 个东西的节点是哪个？递推式f[i][j] = f[[f[i][j-1]][j-1] 比如我们从第i个节点买四个东西的话 那么就是 从第i个节点先买2个到达相应的节点再买4个
我们首先确定每个节点第一个比他大的节点是哪个？然后根据递推式确定以后的f数组，再利用dfs进行儿子的类似操作
千万不要忘记每次dfs 后 f 数组都要进行更新
千万不要忘记每次dfs 后 f 数组都要进行更新
千万不要忘记每次dfs 后 f 数组都要进行更新

#include<bits/stdc++.h>
#define pr printf
#define sc scanf
#define fur(i,a,b) for(int i = a; i<= b ;i++)
#define fdr(i,a,b) for(int i = a; i>= b ;i--)
using namespace std;
typedef long long ll;
const int N = 200005;
int a[N],f[N][20],dep[N],to[N],q,n;
vector <int> v[N];
typedef long long ll;
void dfs(int p,int fa)
{
    // p 是 fa 的儿子
    //首先找第一个比p 大的节点
    int x = fa;
    for(int k = 19;  k>=0 ; k--){
        if(f[x][k] && a[f[x][k]] <=a[p])x=f[x][k];
    }
    if(a[x] > a[p]) f[p][0] = x;
    else f[p][0] = f[x][0];
    for(int i = 1 ; i <20 ;i ++)f[p][i] = f[f[p][i-1]][i-1];
    int num = v[p].size();
    dep[p] = dep[fa] + 1 ;
    for(int i = 0 ; i < num ; i ++){
        int y = v[p][i];
        if(y != fa){
            dfs(y,p);
        }
    }
}
int main()
{
   // freopen("in.txt","r",stdin);
    scanf("%d %d",&n,&q);
    for(int i = 1 ; i<= n ;i++)scanf("%d",&a[i]);
    for(int i = 1 ;i <= n - 1 ; i++){
        int x,y;
        scanf("%d %d",&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;
        scanf("%d %d %d",&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 res = 0 ;
        int x = i + n ;
        for(int k = 19 ; k>=0 ;k --)
        {
            if(dep[f[x][k]]>=dep[to[i]]){
                res += (1<<k);
                x = f[x][k];
            }
        }
        printf("%d\n",res);
    }
    return 0;
}