题目链接：http://codevs.cn/problem/1036/

今天翻箱倒柜的把这题翻出来做了，以前做的时候没怎么理解，所以今天来重做一下

这题是一个LCA裸题，基本上就把另一道裸题小机房的树拿出来改一改就行

但LCA也有两种方式，倍增和tarjan，倍增我个人觉得很好理解，tarjan就有点迷了

所以我就用了两种方式打这一道题

 

倍增：

倍增的做法就是数组f[i][j]表示从i点往上走2^j次方个点可以到达哪个点，

然后进行一个树上倍增，记录下一个深度dep，然后让我们求的两点到同一深度，如果是同一点就return

不是同一点就倍增，倍增这个位置的操作和rmq差不多了，就是找到可以最大跳跃的深度，然后不断找。。直到差一个深度到最近公共祖先

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define maxn 3000510 using namespace std;11 12 struct edge{13 int u,v,nxt;14 }e[maxn*3];15 16 int n,m,a[maxn],now[maxn],f[maxn][33];17 int head[maxn],dep[maxn],vis[maxn],ans;18 19 int tot; 20 void adde(int u,int v){21 e[tot]=(edge){u,v,head[u]};22 head[u]=tot++;23 }24 25 void first(){26 for(int j=1;j<=32;j++){27 for(int i=1;i<=n;i++){28 f[i][j]=f[f[i][j-1]][j-1];29 }30 }31 }32 33 void build(int u){ 34 for(int i=head[u];i!=-1;i=e[i].nxt){35 int v=e[i].v;36 if(!vis[v]){37 f[v][0]=u;38 dep[v]=dep[u]+1;39 vis[v]=1;40 build(v);41 }42 }43 }44 45 int up(int x,int d){46 for(int i=1;i<=d;i++)47 x=f[x][0];48 return x;49 }50 51 int find(int x,int y){52 if(dep[x]
              
               =0;j--){59 if(f[x][j]!=f[y][j]){60 x=f[x][j];y=f[y][j];61 }62 }63 return f[x][0];64 }65 66 int main(){67 memset(head,-1,sizeof(head));68 memset(dep,0,sizeof(dep));69 scanf("%d",&n);70 for(int i=1;i
              
             
            
           
          
         
        
       
      

 

 

tarjan：

虽然有些大佬觉得tarjan比倍增好理解，可能是由于我太弱导致我不能理解tarjan，说实话我觉得tarjan这个算法本身就很迷

tarjan的步骤：

1.判断与u相连的点，如果没来过就继续往深搜索下去

2.用并查集维护u,v的关系，讲两个点合并，将v标记来过

3.查找与u有询问关系的点，如果那个点已经被标记来过就继续

4.这时候找到的v的所属的并查集数组fa[v]储存的就是u,v的最近公共祖先

5.这时候u,v的距离就是u的深度+v的深度-两个最近公共祖先深度

　　dep[u]+dep[v]-2*dep[fa[v]];

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #define maxn 3000510 using namespace std;11 12 struct node{13 int u,v,nxt,w;14 }e[maxn*2],q[maxn*2];15 16 int ans,n,m,head[maxn],heaq[maxn],dep[maxn];17 int low[maxn],dfn[maxn],fa[maxn],num;18 int now[maxn],cnt,vis[maxn],vise[maxn];19 20 int tot;21 void adde(int u,int v){22 e[tot]=(node){u,v,head[u],0};23 head[u]=tot;tot++;24 }25 26 int toq;27 void addp(int u,int v,int w){28 q[toq]=(node){u,v,heaq[u],w};29 heaq[u]=toq;toq++;30 }31 32 int find(int x){33 if(x==fa[x])return x;34 return fa[x]=find(fa[x]);35 }36 37 void tarjan(int u){38 num++;fa[u]=u;39 dfn[u]=low[u]=num;vis[u]=1;40 for(int i=head[u];i!=-1;i=e[i].nxt){41 int v=e[i].v;42 if(!dfn[v]){43 dep[v]=dep[u]+1;44 tarjan(v);45 fa[v]=u;46 }47 }48 for(int i=heaq[u];i!=-1;i=q[i].nxt ){49 int v=q[i].v;50 if(vis[v]&&!vise[q[i].w]){51 vise[q[i].w]=1;52 ans+=dep[v]+dep[u]-2*dep[find(v)];53 }54 }55 56 }57 58 int main(){59 memset(head,-1,sizeof(head));60 memset(heaq,-1,sizeof(heaq));61 scanf("%d",&n);62 for(int i=1;i
             
            
           
          
         
        
       
      

我一个同学教导我，如果你tarjan不理解就画图推，还是推不出来就背就行了，反正又不难背