POJ.1330 Nearest Common Ancestors (LCA 倍增)

题意分析

给出一棵树，树上有n个点(n-1)条边，n-1个父子的边的关系a-b。接下来给出xy,求出xy的lca节点编号。

LCA裸题，用倍增思想。

代码总览

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#define nmax 80520

#define demen 25

using namespace std;

int fa[nmax][demen],head[nmax],dep[nmax];

int n,m,tot = 0;

struct node{

    int to;

    int next;

    int w;

}edge[nmax];

void add(int u, int v){

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void dfs(int rt,int f){

    fa[rt][0] = f;

    for(int i = 1;i<=20;++i){

        fa[rt][i] = fa[fa[rt][i-1]][i-1];

    }

    for(int i = head[rt];i!=-1;i = edge[i].next){

        int nxt = edge[i].to;

        if(nxt != f){

            dep[nxt] = dep[rt] + 1;

            dfs(nxt,rt);

        }

    }

}

int lca(int x, int y){

    int X = x,Y=y;

    if(dep[x] < dep[y]) swap(x,y);

    int dis = dep[x] - dep[y];

    for(int i = 20;i>=0;--i){

        if((1<<i) & dis)

            x = fa[x][i];

    }

    if(x == y) return(x);

    for(int i = 20;i>=0;--i){

        if(fa[x][i] != fa[y][i]){

            x = fa[x][i],y = fa[y][i];

        }

    }

    return(fa[x][0]);

}

void init(){

    memset(fa,0,sizeof fa);

    memset(head,-1,sizeof head);

    memset(dep,0,sizeof dep);

    tot = 0;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--){

        init();

        int n,u,v;

        scanf("%d",&n);

        int root = 0;

        for(int i = 0;i<n-1;++i){

            scanf("%d %d",&u,&v);

            if(root == 0) root = u;

            add(u,v);

            add(v,u);

        }

        dep[root] = 1;

        dfs(root,0);

        scanf("%d %d",&u,&v);

        printf("%d\n",lca(u,v));

    }

    return 0;

}