算法笔记--lca倍增算法

时间：2023-03-10 01:48:22
算法笔记--lca倍增算法

算法笔记

模板：

vector<int>g[N];

vector<int>edge[N];

int anc[][N];

int deep[N];

int h[N];

void dfs(int o,int u,int w)

{

    if(u!=o)deep[u]=deep[o]+,h[u]=h[o]+w;

    for(int j=;j<g[u].size();j++)

    {

        if(g[u][j]!=o)

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j],edge[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

int dis(int u,int v)

{

    int l=lca(u,v);

    return h[u]+h[v]-*h[l];

}

例题：

1.CODEVS 2370 小机房的树

带权lca

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int INF=0x3f3f3f3f;

const int N=5e4+;

vector<int>g[N];

vector<int>edge[N];

int anc[][N];

int deep[N];

int h[N];

void dfs(int o,int u,int w)

{

    if(u!=o)deep[u]=deep[o]+,h[u]=h[o]+w;

    for(int j=;j<g[u].size();j++)

    {

        if(g[u][j]!=o)

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j],edge[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

int dis(int u,int v)

{

    int l=lca(u,v);

    return h[u]+h[v]-*h[l];

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,u,v,c,m;

    cin>>n;

    for(int i=;i<n-;i++)

    {

        cin>>u>>v>>c;

        g[u].push_back(v);

        g[v].push_back(u);

        edge[u].push_back(c);

        edge[v].push_back(c);

    }

    cin>>m;

    for(int i=;i<;i++)anc[i][]=;

    dfs(,,);

    while(m--)

    {

        cin>>u>>v;

        cout<<dis(u,v)<<endl;

    }

    return ;

}

2.CODEVS 1036 商务旅行

普通lca

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ls rt<<1,l,m

#define rs rt<<1|1,m+1,r

const int INF=0x3f3f3f3f;

const int N=1e5+;

vector<int>g[N];

int anc[][N];

int deep[N];

void dfs(int o,int u)

{

    if(o!=u)deep[u]=deep[o]+;

    for(int j=;j<g[u].size();j++)

    {

        if(o!=g[u][j])

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

int dis(int u,int v)

{

    return deep[u]+deep[v]-*deep[lca(u,v)];

}

void init()

{

    for(int i=;i<;i++)anc[][]=;

    dfs(,);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,m;

    cin>>n;

    for(int i=;i<n;i++)

    {

        int a,b;

        cin>>a>>b;

        g[a].push_back(b);

        g[b].push_back(a);

    }

    init();

    cin>>m;

    int a,b,ans=;

    cin>>a;

    for(int i=;i<m;i++)

    {

        cin>>b;

        ans+=dis(a,b);

        a=b;

    }

    cout<<ans<<endl;

    return ;

}

3.METO CODE P223 拉力赛

带权lca,当lca(a,b)==a时，韵韵才能参加。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define ls rt<<1,l,m

#define rs rt<<1|1,m+1,r

#define pb push_back

const int INF=0x3f3f3f3f;

const int N=1e4+;

vector<int>g[N];

vector<ll>edge[N];

int anc[][N];

int deep[N];

ll h[N];

bool vis[N]={false};

int s;

void dfs(int o,int u,ll w)

{

    if(o!=u)deep[u]=deep[o]+,h[u]=h[o]+w;

    for(int j=;j<g[u].size();j++)

    {

        if(g[u][j]!=o)

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j],edge[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

ll dis(int u,int v)

{

    return h[u]+h[v]-*h[lca(u,v)];

}

void init()

{

    for(int i=;i<;i++)anc[i][]=;

    dfs(,,);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,m,a,b;

    ll t;

    cin>>n>>m;

    for(int i=;i<n;i++)

    {

        cin>>a>>b>>t;

        g[a].pb(b);

        g[b].pb(a);

        edge[a].pb(t);

        edge[b].pb(t);

    }

    init();

    int cnt=;

    ll ans=;

    for(int i=;i<m;i++)

    {

        int a,b;

        cin>>a>>b;

        if(lca(a,b)==a)

        {

            cnt++;

            ans+=h[b]-h[a];

        }

        }

    cout<<cnt<<endl;

    cout<<ans<<endl;

    return ;

}

4.HDU 2586 How far way?

带权lca

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

const int INF=0x3f3f3f3f;

const int N=4e4+;

vector<int>g[N];

vector<int>edge[N];

int deep[N];

int h[N];

int anc[][N];

bool vis[N]={false};

int s=;

void dfs(int o,int u,int w)

{

    deep[u]=deep[o]+;

    h[u]=h[o]+w;

    for(int j=;j<g[u].size();j++)

    {

        if(g[u][j]!=o)

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j],edge[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

ll dis(int u,int v)

{

    return h[u]+h[v]-*h[lca(u,v)];

}

void init()

{

    for(int i=;i<;i++)anc[i][]=;

    dfs(,,);

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int t;

    cin>>t;

    while(t--)

    {

        int n,m,a,b,k;

        cin>>n>>m;

        for(int i=;i<n;i++)

        {

            cin>>a>>b>>k;

            g[a].pb(b);

            g[b].pb(a);

            edge[a].pb(k);

            edge[b].pb(k);

            vis[b]=true;

        }

        init();

        for(int i=;i<m;i++)

        {

            cin>>a>>b;

            cout<<dis(a,b)<<endl;

        }

        //cout<<endl;

    }

    return ;

}

5.ZOJ P3195 Design the city

带权lca，三点之间的最短路径公式h[a]+h[b]+h[c]-h[lca(a,b)]-h[lca(a,c)]-h[lca(b,c)]。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

const int INF=0x3f3f3f3f;

const int N=5e4+;

vector<int>g[N];

vector<int>edge[N];

int deep[N];

int h[N];

int anc[][N];

void dfs(int o,int u,int w)

{

    if(u!=o)deep[u]=deep[o]+,h[u]=h[o]+w;

    for(int j=;j<g[u].size();j++)

    {

        if(g[u][j]!=o)

        {

            anc[][g[u][j]]=u;

            for(int i=;i<;i++)anc[i][g[u][j]]=anc[i-][anc[i-][g[u][j]]];

            dfs(u,g[u][j],edge[u][j]);

        }

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;i--)if(deep[anc[i][u]]>=deep[v])u=anc[i][u];

    if(u==v)return u;

    for(int i=;i>=;i--)if(anc[i][u]!=anc[i][v])u=anc[i][u],v=anc[i][v];

    return anc[][u];

}

int dis(int u,int v)

{

    return h[u]+h[v]-*h[lca(u,v)];

}

void init()

{

    for(int i=;i<;i++)anc[i][]=;

    dfs(,,);

}

int main()

{

    int n,q,a,b,c;

    bool flag=true;

    while(~scanf("%d",&n)&&n)

    {

        if(flag) flag=false;

        else printf("\n");

        for(int i=;i<n;i++)g[i].clear(),edge[i].clear();

        for(int i=;i<n;i++)

        {

            scanf("%d%d%d",&a,&b,&c);

            g[a].pb(b);

            g[b].pb(a);

            edge[a].pb(c);

            edge[b].pb(c);

        }

        init();

        scanf("%d",&q);

        while(q--)

        {

            scanf("%d%d%d",&a,&b,&c);

            printf("%d\n",h[a]+h[b]+h[c]-h[lca(a,b)]-h[lca(a,c)]-h[lca(b,c)]);

        }

    }

    return ;

}

相关文章