$O(log(n))$求第k个父亲节点

\(O(log(n))\)求第k个父亲节点

参考：树上倍增的写法和应用（详细讲解，新手秒懂）

// Created by CAD
#include <bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;
vector<int> g[maxn];
int f[maxn][30],dep[maxn];
int lg[maxn];
void dfs(int x,int fa){             //预处理出深度，父亲节点
    f[x][0]=fa,dep[x]=dep[fa]+1;
    for(int i=1;i<=lg[dep[x]];++i)
        f[x][i]=f[f[x][i-1]][i-1];
    for(auto i:g[x])
        if(i!=fa) dfs(i,x);
}
int k_fa(int x,int k){              //倍增法求x的第k个父亲节点
    for(int i=0;i<=lg[k]-1;++i)
        if((1<<i)&k)
            x=f[x][i];
    return x;
}
int main() {
    int n,r;  scanf("%d%d",&n,&r);
    for(int i=1;i<=n-1;++i){
        int a,b;scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for(int i=1;i<=n;++i)              //预处理出log_2(i)+1的值
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(r,0);
    
    return 0;
}

$O(log(n))$求第k个父亲节点

原文：https://www.cnblogs.com/CADCADCAD/p/13437820.html