【树上倍增】最小瓶颈生成树

r囧r小猫 2024-03-25 20:16 60阅读 0赞

**随便学一下树上倍增，反正闲着也是闲着**

**一周没vpCf，感觉早该414了**

**下周vp abc！**

**至少能开出签到呜呜呜**

[【模板】最小瓶颈生成树（数据加强版） - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意

![be0deb29212a0864aadd1c7b7b8015d4.png][]

思路:

其实就是去求树上某一路径的边的最大值

答案就是max(query(u,lca),query(v,lca))

然后可以用树上倍增维护到第j级祖先的路径的边权的最大值

其实不是很懂

感觉就是板子的嵌套QwQ

感觉以后用着用着应该就会懂了

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    struct ty2{
        int u,v,w;
    }e[mxe<<1];
    bool cmp(ty2 x,ty2 y){
        return x.w<y.w;
    }
    
    int n,m,u,v,w,tot=0,Q;
    int F[mxn][33],mx[mxn][33];
    int head[mxn],f[mxn],dep[mxn];
    void dfs_tree(int u,int fa){
        F[u][0]=fa;
        dep[u]=dep[fa]+1;
        for(int j=1;j<=30;j++){
            F[u][j]=F[F[u][j-1]][j-1];
            mx[u][j]=max(mx[u][j-1],mx[F[u][j-1]][j-1]);
        }
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            mx[edge[i].to][0]=edge[i].w;
            dfs_tree(edge[i].to,u);
        }
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            f[i]=i;
        }
    }
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    int find(int x){
        return f[x]=(x==f[x])?x:find(f[x]);
    }
    void join(int u,int v){
        int f1=find(u),f2=find(v);
        if(f1!=f2) f[f1]=f2;
    }
    void kruskal(){
        int res=0;
        sort(e+1,e+1+m,cmp);
        for(int i=1;i<=m;i++){
            if(find(e[i].u)==find(e[i].v)) continue;
            join(e[i].u,e[i].v);
            add(e[i].u,e[i].v,e[i].w);
            add(e[i].v,e[i].u,e[i].w);
            res+=e[i].w;
        }
    }
    int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(int j=30;j>=0;j--){
            if(dep[F[u][j]]>=dep[v]){
                u=F[u][j];
            }
        }
        if(u==v) return u;
        for(int j=30;j>=0;j--){
            if(F[u][j]!=F[v][j]){
                u=F[u][j];
                v=F[v][j];
            }
        }
        return F[u][0];
    }
    int query(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        int res=-1e9;
        for(int j=30;j>=0;j--){
            if(dep[F[u][j]]>=dep[v]){
                res=max(res,mx[u][j]);
                u=F[u][j];
            }
        }
        return res;
    }
    void solve(){
        cin>>n>>m;
        init();
        for(int i=1;i<=m;i++){
            cin>>u>>v>>w;
            e[i]={u,v,w};
        }
        kruskal();
        dfs_tree(1,0);
        cin>>Q;
        while(Q--){
            cin>>u>>v;
            int t=lca(u,v);
            cout<<max(query(u,t),query(t,v))<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

最后贴一下树上倍增的板子：

void dfs(int u,int fa){
        sz[u]=1;dep[u]=dep[fa]+1;
        F[u][0]=fa;
        for(int i=1;i<=30;i++){
            F[u][i]=F[F[u][i-1]][i-1];
            mx[u][i]=max(mx[u][i-1],mx[F[u][i-1]][i-1]);
        }
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            mx[edge[i].to][0]=edge[i].w;
            dfs(edge[i].to,u);
            sz[u]+=sz[edge[i].to];
        }
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/10/problem/805
[be0deb29212a0864aadd1c7b7b8015d4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/08c4292de94c42ff931d6ddd14bfc17f.png