树链剖分求LCA
一直以为求LCA的方法只有4种。今天再次学会了一种。
当题目空间限制比较严格的情况，例如只允许空间复杂度为O(n)级别。此时只能用Tarjan算法。如果此时又要求在线算法，就可以用树链剖分来做LCA了。
主要思想是这样的。
假设我们要求u与v的LCA。
首先判断u与v是否有子树关系（这里的子树关系指的是一个点是否在另一个点的子树中）。如果有就可以直接输出了。
如果没有，就在重链上进行查找。
先计算出u的重链顶端fu与v的重链顶端fv。接下来取Father[fu]与Father[fv]中较深的那个。假设是u。就把u跳到Father[fu]上去。
之后判断。如果此时的u与v是子树关系了，就可以弹出u了（只有可能u是v的祖先）。
由于树链剖分中，每个点到根节点最多跑logn条重链。所以时间复杂度为O(logn)
代码如下：
type
inf=record
x,next:longint;
end;
var
Tree,Size,Maxn,Chain,Father,Putin,Putout,Depth:array[0..100010] of longint;
//Size记录子树大小，Maxn记录当前节点 Size最大的儿子节点，Chain记录重链顶端，Father记录父亲，Putin记录欧拉序列中入栈时间，Putout为欧拉序列中的出栈时间，Depth记录深度。
etree:array[0..100010] of inf;//tree与etree用链表式存树
n,q,i,u,v,w,root,top:longint;
procedure swap(var a,b:longint);//交换两个元素
var
c:longint;
begin
c:=a;
a:=b;
b:=c;
end;
procedure ins(f,s:longint);//插入边
begin
inc(top);
father[s]:=f;
eTree[top].x:=s;
eTree[top].next:=Tree[f];
Tree[f]:=top;
end;
procedure SizeDepthDFS(x,d:longint);//求子树大小、深度以及欧拉序列
var
v,maxsize:longint;
begin
Depth[x]:=d;
inc(top);
Putin[x]:=top;
v:=Tree[x];
maxsize:=0;
while v<>0 do
begin
SizeDepthDFS(eTree[v].x,d+1);
if Size[eTree[v].x]>maxsize then
begin
maxsize:=Size[eTree[v].x];
Maxn[x]:=eTree[v].x;
end;
inc(Size[x],Size[eTree[v].x]);
v:=eTree[v].next;
end;
inc(Size[x]);
inc(top);
Putout[x]:=top;
end;
procedure ChainDFS(x,now:longint);//树链剖分求重链顶端
var
v:longint;
begin
Chain[x]:=now;
v:=tree[x];
while v<>0 do
begin
if eTree[v].x<>Maxn[x] then ChainDFS(eTree[v].x,eTree[v].x)
else ChainDFS(eTree[v].x,now);
v:=eTree[v].next;
end;
end;
function Subtree(s,f:longint):boolean;//判断s是否在f的子树中，这个可以用欧拉序列来判断
begin
if (Putin[f]<=Putin[s]) and (Putout[s]<=Putout[f]) then exit(true);
exit(false);
end;
function Lca(u,v:longint):longint;//求Lca
var
fu,fv:longint;
begin
if Subtree(u,v) then exit(v);
if Subtree(v,u) then exit(u); //首先判断子树关系
while true do //不断上跳
begin
fu:=Chain[u];
fv:=Chain[v];
if Depth[Father[fu]]<Depth[Father[fv]] then //默认Father[fu]为深度更大的节点
begin
swap(fu,fv);
swap(u,v);
end;
u:=Father[fu]; //往上跳
if Subtree(v,u) then exit(u); //如果存在子树关系就可以弹出了
end;
end;
begin
read(n);
for i:=1 to n-1 do
begin
read(u,v);
ins(u,v);//读入
end;
top:=0;
root:=1;//默认根为1
SizeDepthDFS(root,1);//求出以该点为根节点的子树大小Size与该点的深度Depth，顺便搞出欧拉序列以判断子树关系
ChainDFS(root,root);//求出该点的重链顶端（如果不在重链上，就视为自己是自己重链的顶端）
read(q);//读入
for i:=1 to q do
begin
read(u,v);
w:=Lca(u,v);//查询
writeln(w);
end;
end.
有点玄学不过事实证明是正确的。
其实理论分析也是可以的。不过懒得证了（好像不会证哈哈？）。反正不失为一种好方法。