CF1706E题解

· · 题解

1 视频题解

（呃，我这边视频没挂）

2 思路

说来你可能不信，看到这题时我还不会 \operatorname{Kruskal} 重构树，于是花了 30 分钟自学了它，然后赛场上 \operatorname{AC} 了这道题……

我们将这条边的编号定义为它的边权。按照升序排序（好像没必要排序哦）后，通过 \operatorname{Kruskal} 生成树算法，连边时断开这条边，而是新建一个点，让这个新点来连接两点，新点的点权为原来连边的权值。这就是 \operatorname{Kruskal} 重构树。

得到 \operatorname{Kruskal} 重构树后，为了 u 和 v 连通，连接的边的最大值的最小值，即为 u 和 v 的最近公共祖先的点权。通过倍增法求出最近公共祖先即可。

对于所有的 i(1\le i<n)，我们可以先求出使 i 和 i+1 连通的代价（设为 ans_i）。然后，建造线段树，预处理出区间最大值。

最后，询问 l,r 本质上就是使 [l,1+1],[l+1,l+2],…[r-1,r] 都连通，那么答案就是 \max_{i=l}^{r-1}ans_i。利用线段树求出即可。

3 代码与记录

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define max_n 200000
int t;
int n;
int m;
int q;
struct L{
    int u,v,w;
}l[max_n+2];
int fa[max_n<<2];
int fi;
int w[max_n<<2];
struct E{
    int v,nx;
}e[max_n<<2];
int ei;
int fir[max_n<<2];
bool vis[max_n<<2];
int de[max_n<<2];
int fat[max_n<<2][22];
int ans[max_n<<2];
int tr[max_n<<4];
int find(int a){
    if(a==fa[a])return a;
    return fa[a]=find(fa[a]);
}
void addedge(int u,int v){
    e[++ei]=(E){v,fir[u]}; fir[u]=ei;
}
void dfs(int u){
    vis[u]=true;
    for(int i=1;i<=20;++i)fat[u][i]=fat[fat[u][i-1]][i-1];
    for(int i=fir[u],v;i;i=e[i].nx){
        v=e[i].v;
        de[v]=de[u]+1;
        fat[v][0]=u;
        dfs(v);
    }
}
int asklca(int u,int v){
    if(de[u]<de[v])swap(u,v);
    for(int i=20;i>=0;--i){
        if(de[fat[u][i]]>=de[v])u=fat[u][i];
    }
    if(u==v)return u;
    for(int i=20;i>=0;--i){
        if(fat[u][i]^fat[v][i]){
            u=fat[u][i];
            v=fat[v][i];
        }
    }
    return fat[u][0];
}
void build(int o,int l,int r){
    if(l>=r){
        tr[o]=ans[l];
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    tr[o]=max(tr[o<<1],tr[o<<1|1]);
}
int query(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return tr[o];
    int res=0;
    int mid=(l+r)>>1;
    if(ql<=mid)res=max(res,query(o<<1,l,mid,ql,qr));
    if(qr>mid)res=max(res,query(o<<1|1,mid+1,r,ql,qr));
    return res;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("CF1706E_1.in","r",stdin);
    freopen("CF1706E_1.out","w",stdout);
    #endif
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=m;++i){
            scanf("%d%d",&l[i].u,&l[i].v);
            l[i].w=i;
        }
        for(int i=1;i<=(n<<1);++i){
            fa[i]=i;
            fir[i]=0;
            vis[i]=false;
        }
        fi=n;
        ei=0;
        for(int i=1,u,v,uf,vf;i<=m;++i){
            u=l[i].u;
            v=l[i].v;
            uf=find(u);
            vf=find(v);
            if(uf!=vf){
                fa[uf]=fa[vf]=++fi;
                w[fi]=l[i].w;
                addedge(fi,uf);
                addedge(fi,vf);
            }
        }
        for(int i=fi;i>n;--i){
            if(!vis[i]){
                de[i]=1;
                fat[i][0]=i;
                dfs(i);
            }
        }
        for(int i=1,l;i<n;++i){
            l=asklca(i,i+1);
            ans[i]=w[l];
        }
        build(1,1,n-1);
        for(int i=1,l,r;i<=q;++i){
            scanf("%d%d",&l,&r);
            if(l==r)printf("0 ");
            else printf("%d ",query(1,1,n-1,l,r-1));
        }
        printf("\n");
    }
    return 0;
}

记录传送门

By dengziyue