LCA模板

      LCA就是求解一棵树上两个节点的最近的共同祖先，主要运用倍增思想来解决问题。

pascal模板

倍增算法 

for j:=1 to k do
for i:=1 to n do
     f[i,j]:=f[f[i,j-1],j-1];
（注：k:=ln(n)/ln(2),循环顺序一定不可以错）

节点深度

（计算节点深度同时计算出从根到节点路径上数字的和）

procedure dfs(x:longint);
begin
  if d[x]>0 then exit;
  if f[x,0]>0 then
  begin
    dfs(f[x,0]);
    d[x]:=d[f[x,0]]+1;
    sum[x]:=sum[f[x,0]]+a[x];
  end
  else begin
    d[x]:=1;
    sum[x]:=0;
  end;
end;

 LCA 

function lca(x,y:longint):longint;
var
  z,i:longint;
begin
  if x=y then exit(x);
  if d[x]<d[y] then begin
    x:=x xor y;
    y:=x xor y;
    x:=x xor y;
  end;
  if f[y,0]=0 then exit(y);
  if d[x]<>d[y] then
  begin
    i:=k;
    repeat
      while d[f[x,i]]>=d[y] do
      x:=f[x,i];
      dec(i);
    until i<0;
  end;
  if x=y then exit(x);
  i:=k;
  repeat
    while f[x,i]<>f[y,i] do
    begin
      x:=f[x,i];
      y:=f[y,i];
    end;
    dec(i);
  until i<0;
  exit(f[x,0]);
end;

       代码一定要理解并记住，明白工作原理。题目就不复习了，LCA之类的题很多，但是对数据进行巧妙的转化，就可以用LCA来解决了。所以建模能力比算法更重要。