用倍增求lca

虽然很久以前就学了树链剖分的lca方法，但是倍增确实简易了许多。

具体思想非常简单：lca即最近公共祖先。最朴素的方法是对于x和y，先让它们到达同一个深度，然后一个一个点的向上跳（也就是找它的父节点）直到到达同一个点为止。这个方法显然太慢，而我们可以很好的用二进制（倍增）来改进它。

利用倍增的思想，每次不是跳一个，而是2^k，其中k >= 0。当然，我们不能随便跳，不然一下跳到根结点也是「同一个点」。因此在这个算法中，先把两个点跳到同一深度，再每次跳到k最大，而不同的点，最后会刚好在LCA下面的两个字节点，再手动向上跳一个即可。

先用dfs预处理，记录深度dep以及fa[x][k]表示x第2^k的祖先。

这里可以交模版。

我的代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 500005;
int fa[N][21],dep[N];
int n,m,s;
struct edge{
  int v,next;
}e[N * 2];
int front[N],cnt = 0;
void AddEdge(int u,int v) {
  e[++cnt].v = v;
  e[cnt].next = front[u];
  front[u] = cnt;
}
void dfs(int x,int fx)
{
  dep[x] = dep[fx] + 1;
  fa[x][0] = fx;
  for (int i = 1;(1<<i) <= dep[x]; i++)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
  for(int i = front[x]; i; i = e[i].next)
  {
    int v = e[i].v;
    if(v != fx)
      dfs(v,x);
  }
}
int lca(int x, int y) {
  if(dep[x] > dep[y])
     swap(x, y);
  for (int i = 20; i >= 0; i--)
  {
    if (dep[x] <= dep[y] - (1<<i))
        y = fa[y][i];
  }
  if (x == y) return x;
  for (int i = 20; i >= 0; i--)
  {
    if(fa[x][i] == fa[y][i]) continue;
    else x = fa[x][i],y = fa[y][i];
  }
  return fa[x][0];
}
int main()
{
  int a,b;
  scanf("%d%d%d",&n,&m,&s);
  for (int i = 1; i < n; i++)
  {
    scanf("%d%d", &a, &b);
    AddEdge(a,b);
    AddEdge(b,a);
  }
  dfs(s, 0);
  for (int i = 1; i <= m; i++)
  {
    scanf("%d%d", &a, &b);
    printf("%d\n", lca(a,b));
  }
  return 0;
}

吐槽一句，不知为何，我在洛谷上有时红名，有时蓝名。