526互联

lca 学习笔记

发布时间 2023-12-22 21:01:31作者: 卡布叻_周深

定义

  • 最近公共祖先简称 \(LCA\)
  • 两个节点的最近公共祖先，就是这两个点的公共祖先里，离根最远的的那个
  • 为了方便，我们记某点集 \(S={v1,v2,...,vn}\) 的最近公共祖先为 \(LCA(v1,v2,...,vn)\) 或 \(LCA(S)\)

LCA的有用的性质

  • \(1.\) \(lca(x)=x\)
  • \(2.\) 每两个点的 \(lca\) 唯一
  • \(3.\) 如果 \(x\) 与 \(y\) 互相不是对方的祖先，则两点位于 \(lca(x,y)\) 的两颗不同子树中
  • \(4.\) \(重要\) 两点的 \(lca\) 定在两点的最短路上 （那么 \(x\) 到 \(y\) 的最短路即为 \(x->...->lca(x,y)->...->y\)）
  • \(5.\) 由第4条可推出，\(d(x,y)=h(x)+h(y)-2h(lca(x,y))\) （d是两点距离，h为点到根的距离）

实现算法

  • 本人只会树剖算法 \(qwq\)
  • 先来两遍 \(dfs\) ，然后 \(lca\) ，属于在线算法，时间复杂度为 \(O(2*n+n*log(n))\)
  • 下面代码求的是两点的 \(lca\)
#include<bits/stdc++.h>
#define endl '\n'
#define int long long 
using namespace std;
const int N=5e5+1;
int n,m,s;
int fa[N],son[N],dep[N],top[N],sz[N];
vector<int>e[N];
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
void dfs1(int x,int father)
{
    fa[x]=father,dep[x]=dep[father]+1,sz[x]=1;
    for(int y:e[x])
        if(y!=father)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[son[x]]<sz[y]) son[x]=y;
        } 
}
void dfs2(int x,int t)
{
    top[x]=t;
    if(!son[x]) return ;
    dfs2(son[x],t);
    for(int y:e[x])
        if(y!=fa[x]&&y!=son[x])
            dfs2(y,y);
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
    return dep[x]<dep[y]?x:y;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int x,y;
    read(n),read(m),read(s);
    for(int i=1;i<n;i++)
        read(x),read(y),
        e[x].push_back(y),
        e[y].push_back(x);
    dfs1(s,0),dfs2(s,s);
    while(m--)
        read(x),read(y),
        cout<<lca(x,y)<<endl;
}
  • 样例输入
    12 5 1
    1 2
    1 3
    1 4
    2 5
    2 6
    3 7
    4 8
    4 9
    6 10
    8 11
    8 12
    5 6
    10 5
    5 9
    7 9
    11 12
  • 样例输出
    2
    2
    1
    1
    8

如何A题

  • \(1.\) 常与 \(线段树\) \(树状数组\) \(最短路\) 等算法同用。
  • \(2.\) \(lca\) 只能在树中使用，否则会 \(RE\) 所以有环图中需要 \(kru\) 重构树
  • \(3.\) 有时用到边权但不好解决时，可以在 \(x\)、\(y\)两点中插入一个点，使其点权为原边权，最后输出点权即可
  • 在 \(货车运输\) 中运用了前两条，详见 货车运输 题解链接
  • \(4.\) 最短路时，两点间最短距离用到前面的 \(性质5\)，例题 Distance Queries 距离咨询
  • \(5.\) 由于我们没有学习倍增的 \(lca\) ，所以有时超时时要用到树状数组的 \(差分\) ，例题DFS 序 3，树上差分 1
    ,通常修改两点最短路径上所有权值时要用到
  • \(Distance Queries 距离咨询\) 代码
#include<bits/stdc++.h>
#define endl '\n'
#define int long long 
#define f t[p]
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=4e5+1;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,m,k,cnt;
int a[N],fa[N],son[N],dep[N],top[N],sz[N],d[N];
int head[N],to[N],nxt[N],w[N],tot;
void add(int x,int y,int z)
{
    nxt[++tot]=head[x];
    to[tot]=y;
    w[tot]=z;
    head[x]=tot;
}
void dfs1(int x,int t)
{
    fa[x]=t,dep[x]=dep[t]+1,sz[x]=1;
    for(int i=head[x],y;i;i=nxt[i])
        if((y=to[i])!=t)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[son[x]]<sz[y]) son[x]=y;
        }
}
void dfs2(int x,int t)
{
    top[x]=t;
    if(!son[x]) return ;
    dfs2(son[x],t);
    for(int i=head[x],y;i;i=nxt[i])
        if((y=to[i])!=fa[x]&&y!=son[x])
            dfs2(y,y);
}
void build(int x)
{
    for(int i=head[x],y;i;i=nxt[i])
        if((y=to[i])!=fa[x]) 
            d[y]=d[x]+w[i],
            build(y);
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
    return dep[x]<dep[y]?x:y;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int x,y,z;char s;
    read(n),read(m);
    while(m--)
        read(x),read(y),read(z),cin>>s,
        add(x,y,z),add(y,x,z);
    dfs1(1,0),dfs2(1,1),build(1);
    read(k);
    while(k--)
        read(x),read(y),
        cout<<(d[x]+d[y]-d[lca(x,y)]*2)<<endl;//x到根节点的距离+y到根节点的距离-2*公共祖先到根节点的距离
}
  • \(DFS 序 3，树上差分 1\) 代码
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
const int N=1e6+10;
template<typename Tp> inline void read(Tp&x)
{
    x=0;register bool z=1;
    register char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') z=0;
    for(;'0'<=c&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x=(z?x:~x+1);
}
int n,m,root,cnt;
int a[N],fa[N],son[N],rk[N],sz[N],in[N],out[N],dep[N],top[N],c1[N],c2[N];
vector<int>e[N];
void dfs1(int x,int t)
{
    fa[x]=t,dep[x]=dep[t]+1,sz[x]=1,in[x]=++cnt,rk[cnt]=x;
    for(int y:e[x])
        if(y!=t)
        {
            dfs1(y,x);
            sz[x]+=sz[y];
            if(sz[son[x]]<sz[y]) son[x]=y;
        } 
    out[x]=cnt;
}
void dfs2(int x,int t)
{
    top[x]=t;
    if(!son[x]) return ;
    dfs2(son[x],t);
    for(int y:e[x])
        if(y!=fa[x]&&y!=son[x])
            dfs2(y,y);
}
int lca(int x,int y)
{
    for(;top[x]!=top[y];x=fa[top[x]])
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
    return dep[x]<dep[y]?x:y;
}
int lowbit(int x){return x&(~x+1);}
void change(int x,int y)
{
    if(x) 
        for(int i=x;i<=n;i+=lowbit(i)) 
            c1[i]+=y,
            c2[i]+=(dep[rk[x]]*y);
}
void change(int x,int y,int z)
{
    int f=lca(x,y);
    change(in[x],z),change(in[y],z),
    change(in[f],~z+1),change(in[fa[f]],~z+1);
}
int ask1(int x)
{
    int ans=0;
    while(x) ans+=c1[x],x-=lowbit(x);
    return ans;
}
int ask2(int x)
{
    int ans=0;
    while(x) ans+=c2[x],x-=lowbit(x);
    return ans;
}
int ask_it(int x) {return (ask1(out[x])-ask1(in[x]-1));}
int ask_tree(int x) {return ask2(out[x])-ask2(in[x]-1)-(dep[x]-1)*ask_it(x);}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int x,y,z,s;
    read(n),read(m),read(root);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<n;i++)
        read(x),read(y),
        e[x].push_back(y),
        e[y].push_back(x);
    dfs1(root,0),dfs2(root,root);
    for(int i=1;i<=n;i++) change(i,i,a[i]);
    while(m--)
    {
        read(s);
        if(s==1) read(x),read(y),read(z),change(x,y,z);
        else if(s==2) read(x),cout<<ask_it(x)<<endl;
        else read(x),cout<<ask_tree(x)<<endl;
    }
}