LCA最近公共祖先问题 倍增

这道题很明显的LCA了

1. 一般求LCA方法

• 先建树,求的
• 如果深度不相同,先把深的那个点向上爬到同一层
• 如果已经跳到相同层了,就一起向上跳,直到

2. 倍增求LCA

• 在1的基础上改进,引入了一个预处理好的表来记录往上跳步的祖先

• 需要先把这个表预处理出来(可以在建树的时候就预处理出跳表)

  void dfs_build(vector<string>& mtx, int u, int father) {
    vis[u] = true;
    level[u] = level[father]+1;          //更新当前递归到的点的深度
    up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上
  
    for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
        up[u][i] = up[up[u][i-1]][i-1];
  
    for(int i=0; i<n; i++) {
        int v = i;
        if(v == u || vis[v] || mtx[u][v] == '0') continue ;
        fa[v] = u;                      //建立父子关系
        dfs_build(mtx, v, u);
    }
  }    

  求LCA

  int lca(int u, int v) {
    if(level[u] > level[v]) swap(u, v);
    for(int i=L; i>=0; i--)
        if(level[u] <= level[v]-(1<<i)) 
            v = up[v][i];
    if(u == v) return u;
    for(int i=L; i>=0; i--)
        if(up[u][i] == up[v][i]) continue ;
        else {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
  }

3. Tarjan求LCA (离线算法)

• 不会

本题代码

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN (2048)
#define ll long long 
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \
    do { \
        cout << "\033[31;1m " << #x << " -> "; \
        err(x); \
    } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO {

    char print_f[105];
    void read() { }
    void print() { putchar('\n'); }

    template <typename T, typename... T2>
        inline void read(T &x, T2 &... oth) {
            x = 0;
            char ch = getchar();
            ll f = 1;
            while (!isdigit(ch)) {
                if (ch == '-') f *= -1; 
                ch = getchar();
            }
            while (isdigit(ch)) {
                x = x * 10 + ch - 48;
                ch = getchar();
            }
            x *= f;
            read(oth...);
        }
    template <typename T, typename... T2>
        inline void print(T x, T2... oth) {
            ll p3=-1;
            if(x<0) putchar('-'), x=-x;
            do{
                print_f[++p3] = x%10 + 48;
            } while(x/=10);
            while(p3>=0) putchar(print_f[p3--]);
            putchar(' ');
            print(oth...);
        }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K;
#if 0 //非倍增的普通求LCA
bool vis[MAXN];
int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点

#define cls(x) (memset(x, false, sizeof(x)))

class Solution {
public:
    int n;

    void init(vector<string>& mtx) {
        n = mtx.size();
        cls(level), cls(fa), cls(vis);
    }

    void dfs_build(vector<string>& mtx, int u, int dep) {
        vis[u] = true;
        level[u] = dep;                     //更新当前递归到的点的深度
        for(int i=0; i<n; i++) {
            int v = i;
            if(v == u || vis[v] || mtx[u][v] == '0') continue ;
            fa[v] = u;                      //建立父子关系
            dfs_build(mtx, v, dep+1);
        }
    }

    int getSplitNode(vector<string>& mtx, int u, int v) {
        init(mtx);
        dfs_build(mtx, 0, 0);               //先dfs建树

        int lu = level[u], lv = level[v];

        while(lu < lv)                      //把u和v爬到同一层
               lv = level[fa[v]], v = fa[v];
        while(lv < lu) 
            lu = level[fa[u]], u = fa[u];

        while(u != v)                       //u和v一起向上爬
            u = fa[u], v = fa[v];
        return u;
    }
};

#else  //倍增求LCA

#define L (20)
bool vis[MAXN];
int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点
int up[MAXN][L+5];                            //跳表

#define cls(x) (memset(x, false, sizeof(x)))

class Solution {
public:
    int n;

    void init(vector<string>& mtx) {
        n = mtx.size();
        cls(level), cls(fa), cls(vis), cls(up);
    }

    void dfs_build(vector<string>& mtx, int u, int father) {
        vis[u] = true;
        level[u] = level[father]+1;          //更新当前递归到的点的深度
        up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上

        for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
            up[u][i] = up[up[u][i-1]][i-1];

        for(int i=0; i<n; i++) {
            int v = i;
            if(v == u || vis[v] || mtx[u][v] == '0') continue ;
            fa[v] = u;                      //建立父子关系
            dfs_build(mtx, v, u);
        }
    }

    int lca(int u, int v) {
        if(level[u] > level[v]) swap(u, v);
        for(int i=L; i>=0; i--)
            if(level[u] <= level[v]-(1<<i)) 
                v = up[v][i];
        if(u == v) return u;
        for(int i=L; i>=0; i--)
            if(up[u][i] == up[v][i]) continue ;
            else {
                u = up[u][i];
                v = up[v][i];
            }
        return up[u][0];
    }

    int getSplitNode(vector<string>& mtx, int u, int v) {
        init(mtx);
#if 0
        fori(0, n-1)
            forj(0, n-1)
                if(mtx[i][j] == '1') printf("%d %d\n", i, j);
#endif
        dfs_build(mtx, 0, 0);               //先dfs建树
#if 0
        forarr(level, 0, n-1, "level");
        forarr(fa, 0, n-1, "fa   ");
#endif
        return lca(u, v);
    }
};

#endif


#if 1
int main() {
#ifdef debug
    freopen("test", "r", stdin);
    // freopen("out_main", "w", stdout);
    clock_t stime = clock();
#endif

    vector<string> mtx = {
        "0110000000","1000101000","1001000000","0010000000","0100000101",
        "0000001000","0100010010","0000100000","0000001000","0000100000"
    };
    Solution s;
    int U = 6, V = 7;
    cout << s.getSplitNode(mtx, U, V);


#ifdef debug
    clock_t etime = clock();
    printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
    return 0;
}


#endif