Posted at 2019-05-05 ICPC

LCA+st表

1. LCA

LCA，即最近公共祖先（Lowest Common Ancestor)，用于解决的问题：树上任意一对点间的距离。

求解LCA常用的两种方法：

1. 静态Tarjan方法

基本思想：毕竟是静态方法嘛，讲究的就是先把询问和树都存起来然后遍历树的时候就直接处理询问。时间复杂度是O(n+m),其中n为点数，m为询问数。

具体操作：假设目前我们需要寻找点a、b的LCA，那么我们在DFS的时候利用并查集，在一个点的DFS return 时将该点的所有子结点都加到它的父节点里面。利用DFS一个子树遍历完才遍历第二个子树的特性，如果当a b 的LCA为c时，当你先遍历了点a,再遍历到b时，你会发现a的父节点已经被并查集更新为c了。此处附上他人的更详细的过程。

板子代码：由于不常用暂略。

2.动态倍增方法

基本思想：说白了就是二进制嘛，只要我预先处理出树上每个节点的往上走1、 2、 4、……2ⁿ层的点，然后让询问的两个点都往上跳，直到深度相同，两点再同时往上跳，此时的点就是要求的公共祖先点了嘛。预处理时间复杂度O(nlog(n))，每次询问的时间复杂度是O(log(n))。

具体操作：同样用DFS，遍历到每个点时，都处理出每个点往上走那么多层的距离。询问时再利用二进制让a b两点跳到同一深度，如果此时父节点不同则继续往上跳，直到父节点相同为止。

板子代码节选：

LL dis[maxn],dep[maxn];
struct Edge{
    int to,dis;
};
vector<Edge> tree[maxn];
int par[maxn][maxm];//最大为2^maxm的深度
void pre_dfs(int fa,int u,int depth,int dist){
    dis[u]=dist;
    dep[u]=depth;//更新点u的深度和到根节点的距离
    if(u==1){
        for(int i=0;i<maxm;i++)par[u][i]=u;//定1为根节点，则往上跳多少都是自身
    }
    else{
        par[u][0]=fa;
        for(int i=1;i<maxm;i++){
            par[u][i]=par[par[u][i-1]][i-1];//2^i层的节点=u往上跳2^i-1层的点再往上跳2^i-1层
        }
    }
    //处理完u之后再进行常规的DFS
    int len=tree[u].size();
    for(int i=0;i<len;i++){
        int v=tree[u][i].to,d=tree[u][i].dis;
        if(v!=fa) pre_dfs(u,v,depth+1,d+dist);
    }
}

int skip(int a,int level){
    for(int i=maxm-1;i>=0;i--){
        if((1<<i)&level){//二进制的思想
            a=par[a][i];
        }
    }
    return a;
}
int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);//保证a比较深
    a=skip(a,dep[a]-dep[b]);
    if(a==b) return a;
    for(int i=maxm-1;i>=0;i--){//也是利用二进制思想从高位往低位逼近的思想
        if(par[a][i]!=par[b][i]){
            a=par[a][i];
            b=par[b][i];
        }
    }
    return par[a][0];
}

3.LCA转化为RMQ问题

基本思想：与Tarjan求法的思想一致，当你从a遍历到b时经过的深度最小的点即为最近公共祖先。之所以能转化为RMQ，是将DFS时产生长度为2 * n - 1的欧拉序列（实际上就是每经过一个点就标一个号，不管是初次访问还是回退时，所以每个点访问两次）当做一个区间，记录每一个点的初次出现的编号first [ i ] , 然后找first [a] 到 first [b] 这段区间中深度最浅的点。参考博客

具体操作及代码见st表部分

2.st表

基本思想：st表与LCA动态倍增算法相似，均是采用的二进制思想，用st [ i ] [ j ]数组来存储 i 到 i+2^j-1,共2^j长度的区间上的最值问题。预处理时间复杂度为O（nlogn) 查询时间为 O(1)，并不支持在线修改。所以基本上就是用来求区间最值的。

具体操作：由于是最值嘛，所以st[i ] [0 ]=i, st[ i ] [ j ]=max (st[ i ] [ j-1 ] , st[ i+ 2^j-1 ] [ j-1 ] ) ，算法也简单，只要记得预处理就完事了。

用st表解决LCA问题的代码：（例题）

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
const int maxn=40004,maxm=20;
struct edge{
    int to;
    LL dis;
    edge(int _to,LL _dis){
        to=_to;
        dis=_dis;
    }
};
LL dis[maxn];
int dep[maxn],first[maxn],oula[maxn*2],st[maxn*2][maxm];
vector<edge> tree[maxn];
int coun,n,m;
void dfs(int fa,int u,int depth,int dist){
    oula[coun++]=u;
    if(first[u]==0) first[u]=coun-1;
    dep[u]=depth;
    dis[u]=dist;
    int len=tree[u].size();
    for(int i=0;i<len;i++){
        int v=tree[u][i].to,d=tree[u][i].dis;
        if(v!=fa) {
            dfs(u,v,depth+1,dist+d);
            oula[coun++]=u;
        }
    }

}
int comp(int a,int b){return dep[a]<dep[b]?a:b;}
void st_init(){
    for(int i=1;i<=n*2;i++){
        st[i][0]=oula[i];
    }
    for(int j=1;j<maxm;j++){
        for(int i=1;i+(1<<j)-1<n*2;i++){
            st[i][j]=comp(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
int lca(int a,int b){
    int l=first[a],r=first[b];
    if(l>r) swap(l,r);
    int k=log2(r-l+1);
    return comp(st[l][k],st[r-(1<<k)+1][k]);
}
int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        int a,b;
        for(int i=1;i<n;i++){

            LL c;
            scanf("%d%d%lld",&a,&b,&c);
            tree[a].push_back(edge(b,c));
            tree[b].push_back(edge(a,c));
        }
        coun=0;
        dfs(0,1,0,0);
        st_init();
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
            int fa=lca(a,b);
            printf("%lld\n",dis[a]+dis[b]-2*dis[fa]);
        }
    }
    return 0;
}

Previous post: sup-004 Docker环境搭建与开发入门 Next post: sup-003 微信小程序开发快速入门

Site-T

SUP-project

LCA+st表

1. LCA

2.st表