树上倍增

有些情况可能不需要LCA访问，可能BFS走一次就行了。

void dfs(int now,int fa){
    d[now]=d[fa]+1;//儿子节点的深度等于父节点的深度+1
    f[now][0]=fa;
    for(int i=1;i<=lg[d[now]];++i)
        f[now][i]=f[f[now][i-1]][i-1];
    for(auto son:e[now])dfs(son,now);
}

//n个节点
//预处理log数组
for(int i=1;i<=n;++i){
    lg[i]=log(i)/log(2)+1;
}

//预处理每个节点的f[i][j],2^j级祖先
d[root]=0
dfs(root,root)

//借助预处理来实现别的操作
//1. LCA
int lca(int x,int y){//节点x,y的最近公共祖先lca(x,y)
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])x=f[x][lg[d[x]-d[y]]-1];
    if(x==y)return x;
    for(int i=lg[d[x]];i>=0;--i)
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0];
}

//2. 有序链上倍增遍历,借助这个语句实现，依旧是从最大开始跳
int now=5;//假设某条件下找节点5的父亲
int fa=now;
for(int i=lg[d[x]];i>=0;--i){
    if(f[fa][i]<=t){//某种条件
        fa=f[fa][i];
    }
}