51nod 2599 最近公共祖先(LCA) （ST表求LCA模闆）

​​51nod 2599 最近公共祖先(LCA)​​

題目

裸 LCA，給一顆 n 個節點， n-1 條邊的樹，m次查詢求任意兩點LCA。

算法介紹

求

可以用離線

算法，算法複雜度O（n + m）。

還有一種離線的算法，預處理O（nlogn），線上查詢O（1）。就是用

表求LCA。

首先介紹歐拉周遊序，給一顆樹，從根節點周遊：

歐拉周遊序為：1 2 3 2 4 2 5 2 1 6 7 6 8 6 1

節點深度 ：0 1 2 1 2 1 2 1 0 1 2 1 2 1 0

如果按照上面的順序走一遍就會發現歐拉序就是 dfs周遊這顆樹經過每個節點的順序。

序列個數為

。

現在記錄下每個節點第一次出現的順序，那麼任意節點的 LCA 就是這兩個點第一次出現的位置之間深度最小的點

（将樹看成一個無向圖，u和v的公共祖先一定在u與v之間的最短路徑上）

算法實作，我們會用到歐拉序，節點深度數組。這兩個都可以對樹進行一次

周遊得到，而求兩點區間最值則可以用

表來預處理一下。注意

表存的是下标，但是比較的時候要用下标對應的深度來比較

實作

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 9999991;
const ull base = 23333;
const int N = 1e4 + 10;

vector<int> tr[N];    // 鄰接表存圖
int vs[N];        // 第 i 次通路節點的編号
int depth[N];       // 第 i 次通路節點的深度
int id[N];        // 在 vs 數組中 i 節點第一次出現的下标
int vis[N];       // 标記數組
int st[N][20];      // 存最小值對應的下标
int n, m, x, y;       // 圖的頂點，查詢次數
int dfs_clock = 1;

// 求歐拉序
void dfs(int u, int d){   // 目前點，它的父節點，點深度
  id[u] = dfs_clock;
  vs[dfs_clock] = u;
  depth[dfs_clock++] = d;
  for(auto x : tr[u]){
    if(vis[x])          // 通路過不再通路
      continue;
    vis[x] = 1;
    dfs(x, d + 1);
    vs[dfs_clock] = u;      // 回溯節點也要記錄
    depth[dfs_clock++] = d;
  }
}

void RMQ(int nn){
  for (int i = 1; i <= nn; i++){
    st[i][0] = i;
  }
  for (int j = 1; (1 << j) <= nn; j++){
    for (int i = 1; i + (1 << j) - 1 <= nn; i++){
      int a = st[i][j-1];
      int b = st[i + (1 << (j - 1))][j - 1];
      if(depth[a] <= depth[b]){    // 存最小深度對應下标
        st[i][j] = a;
      }else{
        st[i][j] = b;
      }
    }
  }
}

int LCA(int u, int v){
  int l = id[u];
  int r = id[v];
  if(l > r)
    swap(l, r);
  int k = log2(r - l + 1);
  int a = st[l][k];
  int b = st[r - (1 << k) + 1][k];
  return depth[a] > depth[b] ? vs[b] : vs[a];
}

int main()
{
  scanf("%d", &n);
  for(int i = 0; i < n-1; i++){
    scanf("%d%d", &x, &y);
    tr[x].push_back(y);
    tr[y].push_back(x);
  }
  vis[1] = 1;
  dfs(1, 0);
  RMQ(dfs_clock - 1);
  scanf("%d", &m);
  while(m--){
    scanf("%d%d", &x, &y);
    printf("%d\n", LCA(x, y));
  }
  return 0;
}

/*
     1   
     2   3
  4 5
5
1 2
1 3
2 4
2 5

vs   : 1 2 4 2 5 2 1 3 1
depth: 0 1 2 1 2 1 0 1 0
id   : 1 2 8 3 5
*/