引入：

比如说要找树上任意两个点的路上的最大值。如果是一般的做法会接近o（n）的搜，从一个点搜到另一个点，但是如果询问多了复杂度就很高了。

然后我们会预处理。预处理是o（n²）的，询问是o（1）的，但是n大了，时间会超，内存也开不下。

这个时候就需要lca了。如果是倍增lca的话。处理是o（nlogn的），询问是o(logn）的，你发现什么东西都log一遍就很简单了。。。

lca：

先说下lca。为什么要用lca，打个比方，如果我们事先知道了一个点往上任何一个点是啥，并且到它的路径上的最大值也知道。当询问两个点时，只需要找到他们两往上第一个相同的点（即为lca），然后把他们两往上的值取个最大值，这就是我们的答案。但是这样处理的话，发现空间开不下，如果n大了不可能开一个n²的数组。这时我们需要倍增算法。

倍增：

如果我们提前知道了每个点往上2 ^k的点，那么一个点往上2 ^ （k + 1）的点，即为它往上2 ^ k的点再往上2 ^ k的点（相当于我们借助一个点往上2 ^ k的点为跳板，再往上跳2 ^ k，即可到达一个点往上2 ^ (k + 1)的点）这样每次寻找一个点往上任何高度的点变为了 log；

就这样维护一遍就可以求了

贴上自己yy的代码：

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 4e4;

const int M = 4e5;

using namespace std;

int h[N],cnt,gra[N][],dep[N];

int maxn[N][],n,m;

struct path{

  int next,to;

  int dis;

}e[M];

void add(int u,int v,int dis){

  e[++cnt].to = v;

  e[cnt].next = h[u];

  e[cnt].dis = dis;

  h[u] = cnt;

}

void dfs(int u,int pre){

    for(int i = h[u];i;i = e[i].next){

        int v = e[i].to;

        if(v == pre)continue;

        gra[v][] = u;//处理出每个点的直接父亲

        maxn[v][] = e[i].dis;//处理出每个点到直接父亲的距离

        dep[v] = dep[u] + ;

        dfs(v,u);

    }

}

int LCA(int x,int y){

    if(dep[x] < dep[y])swap(x,y);

    int flag = false;

    int log;

    for(log = ;( << log) <= dep[x];log++);log--;

    int ans = ;

    for(int i = log;i >= ;i--)

    if(dep[x] - ( << i) >= dep[y]){

        ans = max(ans,maxn[x][i]);

        x = gra[x][i];

    }//把x向上移到和y相同高度

    if(x == y)return ans;//如果y就是lca 直接跳出

    for(int i = log;i >= ;i--){

    if(gra[x][i] && gra[y][i] != gra[x][i]){

        ans = max(ans,maxn[x][i]);x = gra[x][i];

        ans = max(ans,maxn[y][i]);y = gra[y][i];

    }

    }//把x 和 y同时向上移，如果相同，即找到lca

    if(gra[x][])ans = max(ans,maxn[x][]);

    if(gra[y][])ans = max(ans,maxn[y][]);

    if(!gra[x][] && x != y)return -;//如果移到根节点且x ！= y即x，y不在一颗树上返回-1

    return ans;

}

void getMap(){

    scanf("%d %d",&m,&n);

    int a,b,z;

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

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

     add(a,b,z);

     add(b,a,z);

    }

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

     if(!dep[i]){

       dep[i] = ;

    dfs(i,-);

     }

    }

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

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

    if(gra[i][j - ]){

        int a = gra[i][j - ];

        gra[i][j] = gra[a][j - ];

        maxn[i][j] = max(maxn[i][j - ],maxn[a][j - ]);

    }//处理出每个点1 - 2^k的父亲，和路上最大边权；

}

int main(){

    getMap();

    return ;

}

巴特西

Lca 之倍增算法

引入：

lca：

倍增：

贴上自己yy的代码：

最新文章

热门文章