LCA小结

模板 LCA

• 参考博客

  LCA:

   树上两点的最近公共祖先。 求解树上两点间的距离、最大权值边等信息。
  

  LCA的求解方法

   1.离线算法：
  是指首先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解决LCA问题的离线算法，它结合了深度优先遍历和并查集（但是我并不会啊啊啊啊啊啊啊）。
   2.在线算法：
   就是每次询问都要直接给出结果，基本思想是用vector来存与某点相连的其他点，从树的根节点开始dfs , 保证u的深度小于v的深度，不断往上跳 , 直到u=v,得到lca(u,v) 
  

暴力法

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=502;
vector<int>G[N];///存点,G[1]表示与1相连的点
int fa[N],dep[N];///i节点的父节点,i节点的深度
void dfs(int u,int f,int d)///u节点,u节点的父亲节点,u节点的深度
{
    fa[u]=f;
    dep[u]=d;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==f)
            continue;
        dfs(v,u,d+1);
    }
}
void init()
{
    dfs(root,-1,0);
}
int lca(int u,int v)
{
    if(dep[u]>dep[v])///保证u的深度小于v的深度
        swap(u,v);
    while(dep[v]>dep[u])///使uv的深度一样
        v=fa[v];
    while(u!=v)///不断往上,直到u=v,得到lca(u,v)
    {
        u=fa[u];
        v=fa[v];
    }
    return u;
}

倍增法

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int N=502;
const int LOG=18;
vector<int>G[N];///存点,G[1]表示与1相连的点
int p[LOG][N],dep[N];///p[i][j]表示距离j 往上走2^i个点的父节点,i节点的深度
void dfs(int u,int f,int d)
{
    dep[u]=d;
    p[0][u]=f;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i];
        if(v==f)
            continue;
        dfs(v,u,d+1);
    }
}
void init()
{
    dfs(root,-1,0);
    for(int i=0;i<LOG-1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(p[i][j]<0)
                p[i+1][j]=-1;
            else
                p[i+1][j]=p[i][p[i][j]];
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    for(int i=0;i<LOG;i++)
        if(dep[v]-dep[u]>>i&1)
            v=p[i][v];
        if(u==v)
            return u;
        for(int i=LOG-1;i>=0;i--)
        {
            if(p[i][u]!=p[i][v])
            {
                u=p[i][u];
                v=p[i][v];
            }
        }
        return p[0][u];
}

• 简单lca
  HDU 2586:How far away ？
  题意

  输入
  T(T<=10)（代表有T组输入），接下来输入n(2<=n<=40000) 和 m (1<=m<=200),代表有n个节点，m次询问，再接下来，输入n-1次（x,y,l）代表结点x与y了直接相连，之间的距离为l(0 < l<= 40000)，输入m次（a，b）表示查询a到b的距离
  输出
  输出查询结果。

  样例

  Sample Input
  2
  3 2
  1 2 10
  3 1 15
  1 2
  2 3

  2 2
  1 2 100
  1 2
  2 1
  Sample Output
  10
  25
  100
  100

  代码

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int N=40004;
const int LOG=20;
int p[LOG][N],dep[N];///p[i][j]表示距离j 往上走2^i个点的父节点,i节点的深度
int dis[N];///距离
int n;
struct node
{
    int id,l;
    node(int idid=0,int ll=0)
    {
        id=idid;
        l=ll;
    }
};
vector<node>G[N];///存点,G[1]表示与1相连的点
void dfs(int u,int f,int d)
{
    dep[u]=d;
    p[0][u]=f;
    for(int i=0;i<G[u].size();i++)
    {
        int v=G[u][i].id;
        if(v==f)
            continue;
        dis[v]=dis[u]+G[u][i].l;
        dfs(v,u,d+1);
    }
}
void init()
{
    memset(dis,0,sizeof(dis));
    dfs(1,-1,0);
    for(int i=0;i<LOG-1;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(p[i][j]<0)
                p[i+1][j]=-1;
            else
                p[i+1][j]=p[i][p[i][j]];
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v])
        swap(u,v);
    for(int i=0;i<LOG;i++)
    {
        if(dep[v]-dep[u]>>i&1)
            v=p[i][v];
    }
        if(u==v)
            return u;
        for(int i=LOG-1;i>=0;i--)
        {
            if(p[i][u]!=p[i][v])
            {
                u=p[i][u];
                v=p[i][v];
            }
        }
        return p[0][u];
}
int main()
{
    int t,i,j,m,x,y,l,a,b;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d%d",&n,&m);
       for(i=0;i<n;i++)
        G[i].clear();
       for(i=0;i<n-1;i++)
       {
           scanf("%d%d%d",&x,&y,&l);
           G[x].push_back(node(y,l));
           G[y].push_back(node(x,l));
       }
       init();
       for(i=0;i<m;i++)
       {
           scanf("%d%d",&a,&b);
           printf("%d\n",dis[a]+dis[b]-2*dis[lca(a,b)]);
       }
    }
    return 0;
}