最近学了LCA的相关问题在此总结下

在有根树中,两个节点u和v的公共祖先中距离最近的那个成为其最近公共祖先,在树上两点因为存在唯一的最短路,故其LCA为最短路上深度最小的点。通过求解LCA我们可以处理如求解树或DAG上任意两点的最短距离,将RMQ转化为LCA,结合树链剖分操作等。
求解$LCA$的各种方法全部以HDU 2586为例(自娱自乐)

Tarjan离线处理

离线$ tarjan$的思想是在处理完以$ u$为根的子树时,就将该子树和父亲节点$ u$合并,这样处理完子树后就可以回答所有关于$ u$的询问,前提是询问的节点都是已经被访问过的。为此我们需要为查询建立一颗查询树并存好询问顺序。

Tarjan代码

[cpp]
const int maxn = 40000+7;
const int maxQ = 200+7;
using namespace std;
int rank[maxn];
int par[maxn];
int find(int x) {
if(par[x]==-1) return x;
return par[x]=find(par[x]);
}
void merge(int x,int y) {
x = find(x), y = find(y);
if(x==y) return ;
if(rank[x]<rank[y]) par[x]=y;
else {
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
}
}
int dis[maxn];
bool vis[maxn];//访问标记
struct Edge {
int to,next,w;
}e[maxn<<1];
int tot=0, head[maxn];
void addedge(int u,int v,int w) {
e[tot].to =v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot++;
}
vector query[maxn];
vector num[maxn];
int ans[maxn];
void init() {
tot=0;
memset(vis,0, sizeof(vis));
memset(head,-1, sizeof(head));
memset(dis,0,sizeof(dis));
memset(ans,0, sizeof(ans));
memset(rank,0,sizeof(rank));
for(int i=0;i<maxn;i++) {
query[i].clear();
num[i].clear();
}
}
void tarjan(int u,int val) {
vis[u]=1;
dis[u]=val;
for(int i=head[u];~i;i=e[i].next) {
int to = e[i].to;
if(vis[to]) continue;
tarjan(to,val+e[i].w);
merge(u,to);//当遍历完一棵子树就将该子树和父亲节点u合并
}
for(int i=0;i<query[u].size();i++) {//处理完u节点的子树就可以回答有关u的询问
int to = query[u][i];
if(vis[to]==0) continue;//如果to被访问过就可以回答这个询问
ans[num[u][i]] = dis[u]+dis[to]-2*dis[find(to)];//find(to)就是lca(u,i)
}
}
int main()
{
int t;scanf(“%d”,&t);
while(t–) {
init();
int n,m;scanf(“%d%d”,&n,&m);
for(int i=0;i<=n;i++) par[i] = i;
for(int i=1;i<n;i++) {
int a,b,c;scanf(“%d%d%d”,&a,&b,&c);
addedge(a,b,c);
addedge(b,a,c);
}
for(int i=0;i<m;i++) {
int n1,n2;scanf(“%d%d”,&n1,&n2);
query[n1].push_back(n2);
num[n1].push_back(i);//记录回答顺序
}
tarjan(1,0);
for(int i=0;i<m;i++)
printf(“%d\n”,ans[i]);
}
}
[/cpp]

ST+dfs求解LCA

该算法是将$LCA$转换成$RMQ$问题,好处是通过对区间预处理能高效$O(1)$在线回答,所用思想是将树形结构通过欧拉游记录任意节点的深度,其子树规模,及欧拉序。
这里我废话下$ LCA$与$RMQ$的关系,老是会忘是不是无药可救了。

  • $LCA$与$RMQ$相关的思考:
    $RMQ=>LCA$考虑建立笛卡尔树的过程是不断划分最小值按照深度往大的方向建里
    在建立的过程中,不断按照当前区间的最值来划分。
    所以对于期间$[i,j]$的$ RMQ$,我们同样可以这样来处理,对于处理好的笛卡尔树来说,每个区间的最小值都能很方便的得出。记整个区间的最小值的位置为$ pos$,1如果$pos$在$[i,j]$内的话这次$RMQ$就是$ pos$对应的值,2如果$ pos<[i,j]$的话我们把整个区间的考量缩小到$ [pos+1,N]$而这个区间的最小值按上述所说方便求取,2如果$ pos>[i,j]$的话同2一样处理。如此发现求取$RMQ$的过程与笛卡尔树建立的过程十分相似,而且我们每次总是一一的划分,所以这个过程就相当于求取$[i,j]$的公共祖先,因为在求取的过程中最值的深度是由小变大的,因此这样不超过$ O(logN)$次就能求的任意两点的$LCA$,同时也是序列$[i,j]$的$RMQ$了;然而求取$RMQ$还有很多更加方便的方法因此了解即可。

  • $LCA=>RMQ$感觉这才是这二者精巧处,使用了$Euler \ tour$的$dfs$来记录欧拉序列,深度序列和每个节点出现的时间(时间戳);
    对一棵树$dfs$处理完成后由$dfs$的性质对于节点$u, v$,他们的$ LCA$一定出现在他们第一次出现的两个值的中间而且只出现一次,且是时间戳数组中$pos[u]$~$ pos[v]$中深度最小的那个,至于为什么还是基于$dfs$时的回溯必然要通过他们的祖先,在祖先中选取深度最小的即是他们的$LCA$。

  • 下面讲讲$ST$算法的两种实现
    一般的$RMQ$的$ST$是基于倍增算法设计的$ <O(Nlog_2 N)−O(1)>$的在线算法,
    从每个元素开始取连续的长度为$2^k$ 的区间元素的最小值
    对于$RMQ$的$[i,j]$我们总能找到两端$2^k$ 来覆盖这个区间故可以$O(1)$的回答区间最值
    利用倍增的思想我们可以在$O(Nlog_2 N)$的时间内预处理出长度为$2$的幂次的区间的最值,因为一个长度为$2^k $的区间能被划分成两个$2^(k−1)$ 的区间因此可以设计出状态转移方程
    下面说说$ ±RMQ $所谓约束$RMQ$就是序列种任意两个相邻数为$±1$,算法的核心在于分块的处理以$l=(log_2 N)/2 $的块把$B$序列划分成$M=N/l$ 块,设第$ k$的最小值记为$blockMin(k)$, $±RMQ$的最值就由三部分组成 $block−RMQ$ and $in−RMQ$ 复杂度分析来看$block-RMQ$的复杂度$<O(Mlog_2 M)−O(1)>$
    $Mlog_2 M = \frac{2N}{log_2 N} log_2 M < \frac{2N}{log_2 N} log_2 N=O(n)) $
    $ST+dfs$ 的$<O(nlogn),O(1)>$的代码
    [cpp]
    #include<bits/stdc++.h>
    const int maxn = 40000+111;
    using namespace std;
    int dp[maxn<<1][25];
    int ver[maxn<<1];
    int dep[maxn<<1];
    int vis[maxn];
    int dir[maxn];
    int first[maxn];
    int head[maxn];
    int tot,cnt;
    struct Edge {
    int to, next, w;
    }edge[maxn<<1];
    void addedge(int u,int v,int w) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    edge[tot].w = w;
    head[u] = tot++;
    }
    void init()
    {
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
    memset(dir,0, sizeof(dir));
    dir[1]=0;
    cnt = tot = 0;
    }
    void dfs(int u,int dfn) {
    vis[u]=1;ver[++cnt] = u;first[u]=cnt;dep[cnt]=dfn;
    for(int i = head[u];~i;i=edge[i].next) {
    int v = edge[i].to;
    int w = edge[i].w;
    if(!vis[v]) {
    dir[v] = dir[u] + w;
    dfs(v,dfn+1);
    ver[++cnt] = u;
    dep[cnt] = dfn;
    }
    }
    }
    void ST(int n) {
    int k = int (log2(n));
    for(int i=1;i<=n;i++) dp[i][0]=i;
    for(int j=1;j<=k;j++)
    for(int i=1;i+(1<<j)-1<=n;i++) {
    int a = dp[i][j-1];
    int b = dp[i+(1<<(j-1))][j-1];
    if(dep[a]<dep[b]) dp[i][j]=a;
    else dp[i][j]=b;
    }
    }
    int RMQ(int l,int r) {
    int k = int(log2(r-l+1.0));
    int a = dp[l][k];
    int b = dp[r-(1<<k)+1][k];
    if(dep[a]<dep[b]) return a;
    return b;
    }
    int LCA(int u,int v) {
    int x = first[u], y = first[v];
    if(x>y) swap(x,y);
    return ver[RMQ(x,y)];
    }
    int main() {
    int t;scanf(“%d”,&t);
    while(t–) {
    init();
    int n,m;scanf(“%d %d”,&n,&m);
    for(int i=1;i<n;i++) {
    int a,b,c;
    scanf(“%d %d %d”,&a,&b,&c);
    addedge(a,b,c);
    addedge(b,a,c);
    }
    dfs(1,1);ST(2 * n-1);
    while(m–) {
    int u,v;
    scanf(“%d %d”,&u,&v);
    printf(“%d\n”,dir[u]+dir[v]-dir[LCA(u,v)] * 2);
    }
    }
    }
    [/cpp]

    大材小用的树链剖分求解LCA

    因为树链剖分后得到的元素就能得出LCA所以没有为什么
    实际表明轻重链剖分算法只是对于链式结构有极大的优势,想想也是。具体比较参考2017年国家集训队论文《非常规大小分块算法探究》

[cpp]
#include <bits/stdc++.h>
using namespace std;
const int maxn = 40000+5;
int head[maxn];
int edge_tot;
struct Edge {
int to,next,w;
}edge[maxn<<1];
void addedge(int u,int v,int w) {
edge[edge_tot].to = v;
edge[edge_tot].next = head[u];
edge[edge_tot].w = w;
head[u] = edge_tot ++;
}
int dir[maxn];//点到树根的距离
int son[maxn];//son[u] u 的重儿子
int dep[maxn];//dep[u] u结点的深度 u到root的距离+1
int fa[maxn];//fa[u] u的父亲
int id[maxn]; //剖分后的边在新的数据结构中的位置着重记录一条重链上的相对位置
//这个id[u]存的是(v,u)边的编号v是u其的父亲,也可以代表u的相对编号
int fid[maxn];//与id含义相反
int sz[maxn];//sz[u] 以u为根的子树的size
int Top[maxn];//u所在树链起点 u,v在同一树链中当且仅当Top[u]==Top[v]
int cnt;////已编号数量
void dfs(int u,int pre,int d) {//建有根树 求出sz[],depth[],fa[],son[]
dep[u] = d; fa[u] = pre; sz[u] = 1;
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
int w = edge[i].w;
if(v != pre) {
dir[v] = dir[u] + w;
dfs(v,u,d+1);
sz[u]+=sz[v];
if(son[u]==-1 || sz[v]>sz[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int sp){ //剖分有根树 求出id[], Top[]
Top[u] = sp; //根节点是第一条链
id[u] = cnt ++;
fid[id[u]] = u;
if(son[u]==-1) return;//没有重儿子推出分支
dfs2(son[u], sp);
for(int i=head[u]; ~i; i =edge[i].next) {
int v = edge[i].to;
if(v != son[u] && v != fa[u]) dfs2(v,v);
//其他点的top标号为自身
}
}
int LCA(int x,int y) {
for(;Top[x]!=Top[y];dep[Top[x]]>dep[Top[y]]?x=fa[Top[x]]:y=fa[Top[y]]){}
return dep[x]<dep[y]?x:y;
}
void init() {
memset(son,-1, sizeof(son));
edge_tot = 0;
cnt = 0;//树状数组从1开始
memset(dir,0, sizeof(dir));
memset(head,-1, sizeof(head));
}
int main() {
int t;scanf(“%d”,&t);
while(t–) {
init();
int n,m;scanf(“%d%d”,&n,&m);
for(int i=1;i<n;i++) {
int u,v,k;scanf(“%d%d%d”,&u,&v,&k);
addedge(u,v,k);addedge(v,u,k);
}
dfs(1,0,0);dfs2(1,1);
while(m–) {
int u,v;scanf(“%d%d”,&u,&v);
int short_path = dir[u]+dir[v] -2*dir[LCA(u,v)];
printf(“%d\n”,short_path);
}
}
}

[/cpp]
倍增算法求解LCA待补

分类: LCA图论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.