【每日一题】倍增思想

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
int p[MAXN],h[MAXN],ne[MAXN];//链式前向星写法
int num=0;
const int N = 2e5 + 7;
int n, q, val[N], mrk[N];
int f[N][20], dep[N];
void addEdge(int from, int to){
    p[++num] = to;//to->from
    ne[num] = h[from];
    h[from] = num;
 
    p[++num] = from;
    ne[num] = h[to];
    h[to]=num;
}
//f[u][i]:保存u结点往根方向第2^i个val大于它的结点
void dfs(int u, int father){
    dep[u] = dep[father] + 1;//记录深度
    if (val[u] < val[father]){
        f[u][0] = father;
    }else{
        int x = father;
        for (int i = 19; i >= 0; --i){//x逼近第一个比val[u]大的结点下方的结点
            if (f[x][i] && val[u] >= val[f[x][i]]){
                x = f[x][i];
            }
        }
        f[u][0] = f[x][0];//得到第一个比val[u]大的祖先结点
    }
    for (int i = 1; i <= 19; ++i){//刷新倍增数组
        f[u][i] = f[f[u][i-1]][i-1];
    }
    for(int i=h[u];i!=0;i=ne[i])if(p[i]!=father){
       // f[p[i]][0]=u;
        dfs(p[i],u);
    }
}
int main(void){
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 0; i < n-1; ++i){
        int u, v; cin >> u >> v;
        addEdge(u,v);
    }
    for (int i = 1; i <= q; ++i){
        int u, v, c; cin >> u >> v >> c;
        addEdge(n+i,u);//每个询问新加一个结点连在u下面
        val[n+i] = c, mrk[i] = v;//新结点val设为c，记录目标祖先v
    }
    dep[0]=0;
    dfs(1, 0);//dfs预处理倍增数组
    for (int i = 1; i <= q; ++i){
        int u = n+i, v = mrk[i], ans = 0;
        for (int j = 19; j >= 0; --j){
            if (dep[f[u][j]] >= dep[v]){//用倍增数组，从u往v跳
                u = f[u][j];
                ans += (1<<j);//记录跳了多少步
            }
        }
        cout << ans << endl;
    }
    return 0;
}