LCA（最近公共祖先）——LCA倍增法

一、前人种树

博客：最近公共祖先 LCA 倍增法

博客：浅谈倍增法求LCA

二、沙场练兵

题目：POJ 1330 Nearest Common Ancestors

代码：

const int MAXN = 10010;

const int DEG = 20;

struct Edge

{

  int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void addedge(int u,int v)

{

  edge[tot].to = v;

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

  head[u] = tot++;

}

void init()

{

  tot = 0;

  memset(head,-1,sizeof(head));

}

int fa[MAXN][DEG];//fa[i][j]表示结点i的第2^j个祖先

int deg[MAXN];//深度数组

void BFS(int root)

{

  queue<int>que;

  deg[root] = 0;

  fa[root][0] = root;

  que.push(root);

  while(!que.empty())

  {

    int tmp = que.front();

    que.pop();

    for(int i = 1;i < DEG;i++)

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

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

    {

      int v = edge[i].to;

      if(v == fa[tmp][0])continue;

      deg[v] = deg[tmp] + 1;

      fa[v][0] = tmp;

      que.push(v);

    }

  }

}

int LCA(int u,int v)

{

  if(deg[u] > deg[v])swap(u,v);

  int hu = deg[u], hv = deg[v];

  int tu = u, tv = v;

  for(int det = hv-hu, i = 0; det ;det>>=1, i++)

    if(det&1)

      tv = fa[tv][i];

  if(tu == tv)return tu;

  for(int i = DEG-1; i >= 0; i--)

  {

    if(fa[tu][i] == fa[tv][i])

      continue;

    tu = fa[tu][i];

    tv = fa[tv][i];

  }

  return fa[tu][0];

}

bool flag[MAXN];

int main()

{

    int T;

  int n;

  int u,v;

  scanf("%d",&T);

  while(T--)

  {

    scanf("%d",&n);

    init();

    memset(flag,false,sizeof(flag));

    for(int i = 1;i < n;i++)

    {

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

      addedge(u,v);

      addedge(v,u);

      flag[v] = true;

    }

    int root;

    for(int i = 1;i <= n;i++)

      if(!flag[i])

      {

        root = i;

        break;

      }

    BFS(root);

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

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

  }

    return 0;

}