Aczy156

Algorithm14.4 最近公共祖先(LCA)

[TOC]

LCA最近公共祖先

dfs深搜

  • 更新depth深度数组 depth[maxpoint]
  • 更新p爬升数组 p[maxpoint][21]

LCA

  • 利用depth深度数组来进行爬升之前的微调 => 将两个节点调整到同一高度
  • 利用p数组来进行爬升，获取最近公共祖先

模版 LCA

https://www.luogu.com.cn/problem/P3379

1、数据结构：

  • 链式前向星储存图结构：

用结构体储存to和next，类似于可延展的vector所描述的邻接表

struct node {
  int to, next;
}edge[maxpoint<<1]; int head[maxpoint], tot; // 注意：edge边的数量要开到二倍，因为

添加边 =>利用tot全局索引指引。

void addedge(int from, int to) {
  edge[++tot].to = to;
  edge[tot].next = head[from];
  head[from] = tot;
}
  • LCA的数据结构：depth[maxpoint]和p[maxpoint][21]

dfs构造depth深度数组和p爬升数组

void dfs(int from, int fa) {
  depth[from] = depth[fa] + 1; // 更新depth深度数组
  for (int i = 1; (1<<i) <= depth[from]; ++i) p[from][i] = p[p[from][i-1]][i-1]; // 更新p爬升数组 
  for (int i = head[from]; i; i=edge[i].next) {
    int to = edge[i].to;
    if (to != fa) dfs(to, from);
  }
}

lca使用depth深度数组和p爬升数组

int lca(int a, int b) {
  if (depth[a] > depth[b]) swap(a, b);
  for (int i = 20; i >= 0; i++) if(depth[b]-(1<<i) <= depth[a]) b=p[b][i]; // 调整至a和b到同一高度
  if (a == b) return a;
  for (int i = 20; i >= 0; i++) 
    if (p[a][i] == p[b][i]) continue;
  	else a = p[a][i], b = p[b][i];
  return p[a][0];
}

完整AC代码

#include <iostream>
using namespace std;
#define maxnode 500010
int n, m, root, ta, tb, depth[maxnode], p[maxnode][21];
struct node {
    int to, next;
}edge[maxnode<<1];int head[maxnode],tot;

void addedge(int from, int to) {
    edge[++tot].to = to;
    edge[tot].next = head[from];
    head[from] = tot;
}

void dfs(int from, int fa) {
    depth[from] = depth[fa]+1;
    p[from][0] = fa;
    for (int i = 1; (1<<i) <= depth[from]; ++i) p[from][i] = p[p[from][i-1]][i-1];
    for (int i = head[from]; i; i=edge[i].next) {
        int to = edge[i].to;
        if (to != fa) dfs(to, from);
    }
}

int lca(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    for (int i = 20; i >= 0; --i) if (depth[a] <= depth[b]-(1<<i)) b = p[b][i];
    if (a == b) return a;
    for (int i = 20; i >= 0; --i)
        if (p[a][i] == p[b][i]) continue;
        else a = p[a][i],b=p[b][i];
    return p[a][0];
}


int main() {
    scanf("%d%d%d", &n, &m, &root);
    for (int i = 1; i <= n-1; ++i) {scanf("%d%d", &ta, &tb);addedge(ta, tb);addedge(tb, ta);}
    dfs(root, 0);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &ta, &tb);
        int ans = lca(ta, tb);
        int hh=H[a]+H[b]-H[u]*2+(PZ[u]=='H');
        int gg=G[a]+G[b]-G[u]*2+(PZ[u]=='G');
        if(c=='H'){
            if(hh) printf("1");
            else   printf("0");
        }
        else{
            if(gg) printf("1");
            else   printf("0");
        }
    printf("%d\n", lca(ta, tb));}
    return 0;
}
Posted on Feb 1, 2021