最近公共祖先LCA的三种求法

最近公共祖先的定义：如果结点c满足：

目录

1.向上标记法

2.倍增算法

3.用离线的tarjan算法求LCA 时间复杂度O（n+m）

         1172. 祖孙询问

1171. 距离

---

1.c是a和b的公共祖宗结点。

2.c是距离a，b最近的公共祖宗节点。

那么就称c是a和b的最近公共祖先。

1.向上标记法

分别从a，标记所有a的祖宗节点，再让b向上跳，第一次遇到标记的结点就是最近公共祖先。

n个结点时间复杂度 O（n*n）

2.倍增算法

step1:预处理所有点从上走2的k次幂的父亲是谁，fa[i][j] 表示从i开始向上走2的j次幂能走到的节点其中

0<=j<=log2(n)

同时预处理每个节点的深度depth[i].

step2:求x，y的最近公共祖先：

1.假设x的深度比y大，也即x在y的下面，先让x倍增跳到与y同一深度（枚举2的整数次幂）

2.让两个点同时往上跳，一直跳到最近公共祖先的下一层，答案就是 fa[a][0]或者fa[b][0];

时间复杂度O（n*logn）；

3.用离线的tarjan算法求LCA 时间复杂度O（n+m）

1.利用深度优先遍历将图分为三类同时用并查集得出每个已经遍历过点的代表元：

0.没有访问的点

1.正在搜索的点

2.已经遍历的点

 2.所有与正在搜索点集有关联的的已经遍历过点的最近公共祖先就是这个点的代表元。

注意点：因为是离线算法需要存储每次询问和每次询问的答案。

1172. 祖孙询问​​​​​​​

给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是1∼n。

有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 表示节点个数；

接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 a 就是树的根；

第 n+2 行是一个整数 m 表示询问个数；

接下来 m 行，每行两个不同的正整数 x 和 y，表示一个询问。

输出格式

对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

数据范围

1≤n<=4e4,
1≤每个节点的编号≤4e4

输入样例：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例：

1
0
0
0
2

  裸的LCA，倍增算法。

code：

//利用倍增算法求最近公共祖先
//1.让结点a、b的深度相同
//2.让节点a、b跳到LCA的下一层。
#include<bits/stdc++.h>
using namespace std;
int n,m;
int root;
const int N=4e4+10,M=N*2;
int h[N],e[M],ne[M],idx;
int fa[N][16];
int depth[N];
void add(int a,int b){
  e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int q[N];
void bfs(){
  int hh=0,tt=0;
  memset(depth,0x3f,sizeof depth);
  q[0]=root;
  depth[0]=0;
  depth[root]=1;
  while(hh<=tt){
    int t=q[hh++];
    for(int i=h[t];~i;i=ne[i]){
      int j=e[i];
      if(depth[j]>depth[t]+1){
        depth[j]=depth[t]+1;
        q[++tt]=j;
        fa[j][0]=t;
        for(int k=1;k<=15;k++){
          fa[j][k]=fa[fa[j][k-1]][k-1];
        }
      }
    }
  }
}
int lca(int a,int b){
  if(depth[a]<depth[b]) swap(a,b);
    for(int i=15;i>=0;i--){
      if(depth[fa[a][i]]>=depth[b]){
        a=fa[a][i];
      }
    }
    if(a==b) return a;
    for(int i=15;i>=0;i--){
    if(depth[fa[a][i]]!=depth[fa[b][i]])
      {
        a=fa[a][i];
        b=fa[b][i];
      }
    }
    return fa[a][0];
}
signed  main(){
  cin>>n;
  memset(h,-1,sizeof h);
  for(int i=1;i<=n;i++){
    int a,b;
    cin>>a>>b;
    if(b==-1) root=a;
    else add(a,b),add(b,a);
  } 
  bfs();
  cin>>m;
  while(m--){
    int a,b;
    cin>>a>>b;
    int p=lca(a,b);
    if(p==a) cout<<1<<endl;
    else if(p==b) cout<<2<<endl;
    else cout<<0<<endl;
  }
  return 0;
}

1171. 距离

给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：

• 边是无向的。
• 所有节点的编号是 1,2,…,n

输入格式

第一行为两个整数 n和 m。n表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数x,y，表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式

共 m 行，对于每次询问，输出一行询问结果。

数据范围

2≤n≤1e4
1≤m≤2×1e4
0<k≤100
1≤x,y≤n

输入样例1：

2 2 
1 2 100 
1 2 
2 1

输出样例1：

100
100

输入样例2：

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2：

10
25

思路，对于树上的两个结点x,y间的距离我们可以用公式 dist[x],dist[y] ,dist[lca(x,y)] ,分别表示 x，y，以及x和y的最近公共祖先到根节点的距离。

那么distance=dist[x]+dist[y]-2*dist[lca(x,y)];

code:

//树的tarjan算法离线求LCA
//1.求出树中各点到根节点的距离
//2.用tarjan算法将途中点分类，更新与u有关的节点的LCA更新dist
//
//
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;

const int N = 10010, M = N * 2;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];   // first存查询的另外一个点，second存查询编号

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dist[j] = dist[u] + w[i];
        dfs(j, u);
    }
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;
        }
    }

    for (auto item : query[u])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - dist[anc] * 2;
        }
    }

    st[u] = 2;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a != b)
        {
            query[a].push_back({b, i});
            query[b].push_back({a, i});
        }
    }

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    dfs(1, -1);
    tarjan(1);

    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);

    return 0;
}