倍增这种东西，听起来挺高级，其实功能还没有线段树强大。线段树支持修改、查询，而倍增却不能支持修改，但是代码比线段树简单得多，而且当倍增这种思想被应用到树上时，它的价值就跟坐火箭一样，噌噌噌地往上涨。

关于倍增思想：

倍增的思想很简单：通过区间[1,2^i-1]与[1+2^i-1,2ⁱ(2^i-1+2^i-1)]求出区间[1,2ⁱ]。

所以它可以用于区间求最值，求和。而到了树上之后，就变成了，求它往上任意次的祖先。

而倍增求LCA，就是用到了倍增这个功能。

倍增求LCA算法思路：

f[i,j]，表示结点i，向上跳2^j次跳到的点为f[i,j]。

显然f[i,0]中存的是i结点的父亲。

而f[i,j]=f[f[i,j-1],j-1]，所以我们可以很简单的就求出f数组。

那么我们应该如何用它来求LCA呢？

两个结点a，b。（假设a的深度小于b）

首先我们让两个结点跳到同一深度（那个深度小跳到哪儿），这个过程可以用倍增来加速：从大到小枚举i，判断b往上跳2ⁱ是否会超过a，如果会，就不跳，不会，就跳。

这个为什么对于每个2ⁱ最多只会跳一次呢？

——你跳两次2ⁱ，我不会直接跳一次2ⁱ⁺¹吗，动动脚趾都知道了嘛！

当它们处于同一高度时会产生两种情况：1、a=b，说明a本来就是b的祖先。2、a<>b，这个时候我们也是从大到小枚举i，判断a和b两者都向上跳2ⁱ次（假设此时在结点C，D）会不会重合，若重合，说明它们的LCA在C的下面，不跳，若不重合则说明LCA在C、D的上面，那么就让a跳到C，b跳到D。最后再把a（或b）往上跳1次，就是LCA了！

那么为什么最后要向上跳一次呢？

——如果在某时刻我们往上跳2ⁱ次就能跳到LCA的话，那么C就会与D重合，所以并不会跳上去，而是会往上跳（2^i-1+2^i-2+...+2¹+2⁰）次。所以我们在最后取其父亲就能够得到LCA了。

代码：

var

  f:array[0..100000,0..20]of longint;

  next,dist,vet:array[0..200000]of longint;

  x,y,z,a,b,i,j,k,n,m,tot,ans,sum:longint;

procedure add(x,y,z:longint);

begin

  inc(tot);

  next[tot]:=head[x];

  vet[tot]:=y;

  head[x]:=tot;

  dist[tot]:=z;

end;

procedure dfs(u,dep:longint);

var

  i,v:longint;

begin

  depth[u]:=dep; vis[u]:=true;

  for i:=1 to 20 do

    f[u,i]:=f[f[u,i-1],i-1];

  i:=head[u];

  while i<>0 do

  begin

    v:=vet[i];

    if not vis[v] then

    begin

      f[v,0]:=u;

      dfs(v,dep+1);

    end;

    i:=next[i];

  end;

end;

function lca(a,b:longint):longint;

var

  i,t:longint;

begin

  if depth[a]>depth[b] then begin t:=a; a:=b; b:=t; end;

  for i:=20 downto 0 do

    if depth[f[b,i]]>=depth[a] then b:=f[b,i];

  if a=b then exit(a);

  for i:=20 downto 0 do

    if f[a,i]<>f[b,i] then

    begin

      a:=f[a,i]; b:=f[b,i];

    end;

  exit(f[a,0]);

end;

begin

  read(n);

  for i:=1 to n-1 do

  begin

    read(x,y,z);

    add(x,y,z); add(y,x,z);

  end;

  dfs(1,1);

  read(m);

  for i:=1 to m do

  begin

    read(x,y);

    writeln(lca(x,y));

  end;

end.

巴特西

[学习笔记] 树上倍增求LCA

关于倍增思想：

倍增求LCA算法思路：

代码：

最新文章

热门文章