各种求lca的办法

1.暴力求
2.倍增求
3.用RMQ求
4.用tarjan离线求
5.用树链剖分求
6.（刚看到有一个转成二进制求的）有点懵逼
1.关于暴力
有的时候是很快的（深度比较小），有时可以人为构造（如按秩合并），大部分时间可以被卡过，所以不是个好方法，但暴力出奇迹啊，简单地说就是一个一个往上找。
代码我有个比较优美的

                        x1:=x;
                        while(fa[x1]<>x1)do
                        begin
                                bz[x1]:=true;
                                x1:=fa[x1];
                        end;
                        y1:=y;
                        while(fa[y1]<>y1)do
                        begin
                                if(bz[y1])then
                                begin
                                        break;
                                end;
                                y1:=fa[y1];
                        end;
                        lca:=y1;

2.关于倍增
其实挺简单的，暴力是一个一个往上跳，倍增就是2^n个往上跳。
我们想象一下，如果两个点在同一深度，那么如果它们的第2^n个祖先是不一样的，那么是不是说明lca还在他们2^n之上，那么我们就都跳到他们的第2^n个祖先上，然后再继续找。
但是，如果它们的第2^n个祖先是相等的，并不一定说明这就是它们的lca，因为在它们的lca之上的祖先都是一样的（画个图，理解一下）
只有当n=0，2^0=1,也就是只往上跳一个，然后它们一样的话，那才能说明这是lca。
只要预处理出倍增的数组，然后跳就行了。
至于深度不同，那就把深度较大的点往上跳到深度相同为止。
下面是预处理倍增（注意每个点的父亲要在建图就记录好）

        for i:=1 to 19 do
        begin
                for j:=1 to n do
                begin
                        if(deep[j]>1 shl i)then
                        begin
                                fa[j,i]:=fa[fa[j,i-1],i-1];
                                //它第2^i-1个祖先的2^i-1个祖先就是它的2^i个祖先
                        end;
                end;
        end;

下面是倍增的主程序

                if(deep[x]>deep[wz])then//深度不同
                begin
                        up(x,19);//大的往上跳
                end;
                if(deep[x]<deep[wz])then
                begin
                        up1(wz,19);
                end;
                doubleup(x,wz,19);//一起跳

下面是倍增的过程

procedure up(var x:longint;s:longint);
begin
        while(deep[x]<>deep[wz])do
        begin
                while(fa[x,s]=0)do dec(s);//没有这个祖先
                while(deep[fa[x,s]]<deep[wz])do dec(s);
                ans:=ans+1 shl s;//记录到lca的距离
                x:=fa[x,s];
        end;
end;
procedure up1(var wz:longint;s:longint);//跟上面一样
begin
        while(deep[wz]<>deep[x])do
        begin
                while(fa[wz,s]=0)do dec(s);
                while(deep[fa[wz,s]]<deep[x])do
                begin
                        dec(s);
                end;
                ans:=ans+1 shl s;
                wz:=fa[wz,s];
        end;
end;
procedure doubleup(var x,wz:longint;s:longint);
begin
        while(x<>wz)do
        begin
                while(fa[x,s]=0)do dec(s);
                while(fa[x,s]=fa[wz,s])and(s>0)do dec(s);//相等时一定要s=0才跳
                ans:=ans+(1 shl s)*2;//两个都跳，所以要*2
                x:=fa[x,s];
                wz:=fa[wz,s];
        end;
end;

没了，简洁明了。
3.关于RMQ
刚刚学会，对于一棵树，遍历出欧拉序，什么是欧拉序呢，类似于dfs序，但是返回的时候也要记录
例如

那么欧拉序就是
1 2 4 2 5 2 1 3 1
就是dfs的顺序嘛
然后记录下每个点第一次出现的地方。
1第一次出现在1
2第一次出现在2
3第一次出现在8
4第一次出现在3
5第一次出现在5
然后对与某两个的lca就是在它们第一次出现地方之间找一个深度最小的，用RMQ维护（线段树慢）
例如，3 5的lca，就是5 2 1 3里深度最小的1，
4 5 的lca就是4 2 5里深度最小的2
别的我还不会，太弱了。。。