看了好多dalao的博客，就总结一下啦ovo

tarjian算法很是神奇，它的作用是求lca。它是一种离线算法。

在线是指输入一个询问输出一个结果。

离线是将询问一次性输入，一起处理。

tarjan它是将m个询问打乱顺序，在每个结点上挂上它的询问,利用dfs和并查集进行处理。

对于一个结点u，如果要找(u,v)的lca，u和v的关系分为以下几种情况：

（1）结点v在u的子树中，那么lca(u,v)=u;

 (2)  结点v不在u的子树中，那么v就在u子结点以外的结点中。v可能在u的爸爸的子树中，那么lca(u,v)=u的爸爸；

（3）如果v不在u的爸爸的子树中，那么v可能在u的爸爸的爸爸的子树中，lca(u,v)=u的爸爸的爸爸；

发现找爸爸的过程好像和并查集的操作很像哦.

【代码】

#include
     
      using namespace std;#define N 10000vector
      
       vec[N];vector
       
        que[N];int dad[N],far[N],qx[N],qy[N];int n,m,x,y,ans[N];int f(int x){    return far[x]==x?x:far[x]=f(far[x]);    }void dfs(int x){    far[x]=x;    for(int i=0;i