倍增算法

说明

效率较高的一种求LCA的方法,在线查询,通过二进制的方式降低复杂度,推荐使用

原理讲解:LCA-倍增法(在线)O(nlogn)-O(logn)

使用方法

  1. init()
  2. addedge() 需要双向加边
  3. DFS/BFS
  4. LCA(x, y)返回x和y的LCA

Tips

  1. 推荐使用该方法查询LCA
  2. 树的根节点要根据具体情况来定
  3. 如使用DFS处理,可以调用get_kth_anc(int x , int k)来查找x的第k个祖先,但是可能会爆栈

模版

#pragma comment(linker, "/STACK:10240000000,10240000000")///扩栈,要用c++交,用g++交并没有什么卵用。。。
int n , m , he[maxn] ,rt[maxn], ecnt;
bool vis[maxn];
struct edge{
    int v , next;
} e[maxn << 1];

int dep[maxn] , f[20][maxn] , Lev , s[maxn];///1<<20 < N, f[j][i] 表示i的第2^j个祖先 最多可容纳100w的节点数量

void dfs(int x , int fa){///也可以用bfs,但bfs不能统计节点孩子个数
    dep[x] = dep[fa] + 1;
    f[0][x] = fa , s[x] = 1;
    for (int i = he[x] ; ~i ; i = e[i].next){
        int y = e[i].x;
        if (y != fa){
            dfs(y , x);
            s[x] += s[y];///节点x的孩子个数
        }
    }
}
void bfs(int rt)///不需要求孩子个数,同时防止暴栈
{
    queue<int> q;
    q.push(rt);
    f[0][rt] = 0,dep[rt] = 1,vis[rt] = 1;
    while(!q.empty()){
        int fa = q.front();
        q.pop();
        for (int i = he[fa] ; ~i ; i = e[i].next){
            int v = e[i].v;
            if (!vis[v]){
                dep[v] = dep[fa] + 1;
                f[0][v] = fa ,vis[v] = 1;
                q.push(v);
            }
        }
    }
}
int LCA(int x , int y){
    if (dep[x] > dep[y]) swap(x , y);
    for (int i = Lev ; i >= 0 ; -- i)///找y的第dep[y] - dep[x]个祖先
        if (dep[y] - dep[x] >> i & 1)
            y = f[i][y];
    if (x == y) return y;
    for (int i = Lev ; i >= 0 ; -- i)
        if (f[i][x] != f[i][y])
            x = f[i][x] , y = f[i][y];
    return f[0][x];
}
int get_kth_anc(int x , int k){ ///找x的第k个祖先
    for (int i = 0 ; i <= Lev ; ++ i)
        if (k >> i & 1)
            x = f[i][x];
    return x;
}
void init(){
    memset(he , -1 , sizeof(he));
    memset(rt,0,sizeof(rt));
    ecnt = 0;
}
void adde(int u,int v){
    e[ecnt].v = v;
    e[ecnt].next = he[u];
    he[u] = ecnt ++;
}
void work(){
    int i , j , x , y , z,anc;
    init();
    scanf("%d",&n);
    for (i = 1 ; i < n ; ++ i){
        scanf("%d%d",&x,&y);
        adde(x,y);
        adde(y,x);
        rt[y]  =x;
    }
    for(int i=1; i<=n; i++){
        if(rt[i]==0){
            anc = i;    //确定树的根节点
            break;
        }
    }
    dfs(anc , 0);
    for (j = 1 ; 1 << j < n ; ++ j)
        for (i = 1 ; i <= n ; ++ i)
            f[j][i] = f[j - 1][f[j - 1][i]];
    Lev = j - 1;

    int q;
    scanf("%d",&q);
    while (q--) {
        scanf("%d%d",&x,&y);
        if (dep[x] < dep[y])
            swap(x , y);
        printf("%d\n",LCA(x , y));
    }
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        work();
    }
    return 0;
}

results matching ""

    No results matching ""