学步园

【题意】

给定一棵树，两个节点的最早公共祖先

【输入】

第一行一个t表示数据组数

每组数据第一行一个n表示点数

接下来n-1行描述树，a b，表示b的父节点是a

之后一行a b表示询问a和b的最早公共祖先

【输出】

回答每组数据的询问

裸的lca问题，实际上由于只有一次询问，随便搞搞就行了，为了锻炼一下代码能力，写了个log级支持多组询问的程序，1A

program poj1330;
var
  who,a,b,tot,t,n,i,j,k:longint;
  height,next,point,root:array [0..10001] of longint;
  top:array [0..10001] of boolean;
  father:array [0..15,0..10001] of longint;

procedure swap (var a,b:longint);inline;
var
  i:longint;
begin
  i:=a;
  a:=b;
  b:=i;
end;

function lca (a,b:longint):longint;inline;
var
  i:longint;
begin
  if height[a]<height[b] then swap(a,b);
  while height[a]<>height[b] do
    a:=father[trunc(ln(height[a]-height[b])/ln(2)),a];
  if a=b then exit(a);
  i:=trunc(ln(height[a])/ln(2))+1;
  repeat
    if father[0,a]=father[0,b] then exit(father[0,a]);
    while father[i,a]=father[i,b] do dec(i);
    a:=father[i,a];
    b:=father[i,b];
  until false;
end;

procedure connect (u,v:longint);inline;
begin
  inc(tot);
  point[tot]:=v;
  next[tot]:=root[u];
  root[u]:=tot;
end;

procedure dfs (now,last,high:longint);
var
  i:longint;
begin
  height[now]:=high;
  father[0,now]:=last;
  i:=0;
  while 1 shl i<high do
    begin
      father[i+1,now]:=father[i,father[i,now]];
      inc(i);
    end;
  father[i,now]:=who;
  i:=root[now];
  while i<>0 do
    begin
      dfs(point[i],now,high+1);
      i:=next[i];
    end;
end;

begin
  read(t);
  while t>0 do
    begin
      dec(t);
      fillchar(root,sizeof(root),0);
      fillchar(top,sizeof(top),true);
      fillchar(father,sizeof(father),0);
      tot:=0;
      read(n);
      for i:=1 to n-1 do
        begin
          read(a,b);
          connect(a,b);
          top[b]:=false;
        end;
      for who:=1 to n do
        if top[who] then break;
      dfs(who,0,1);
      read(a,b);
      writeln(lca(a,b));
    end;
end.