kruskal重构树

应用

解决类似从某点v开始经过不超过边权x的边所能到达的节点的问题。

原理

在\(kruskal\)过程中，如果有边\((u,v,w)\),其所属两个集合的根为\(uu,vv\)并且不相同，那么就新建一个节点\(p\)，将\(p\)的点权值设为\(w\)，并将\(p\)于\(u,v\)连边。

最后构成了一棵树，即\(kruskal\)重构树。(因为一共\(n\)个点的原图生成树一共有\(n-1\)条边，对应\(n-1\)个新点，而每个新点连出\(2\)条新边，所以重构树一共\(2n-1\)个点，\(2n-2\)条边)

当询问从\(v\)经过\(\leq x\)的边走过的节点时，只需要从\(v\)向上倍增找到点权\(\leq x\)的点权最大的点，维护这个点的子树即可。

P4197 & P7834

转化为\(kruskal\)重构树后，发现树的每个节点对应一个区间，而询问就是问一个区间的第\(k\)大，主席树即可。

注意到空间卡的比较死，所以离散化一下。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10,M=5e5+10,K=22,INF=1e6+10;
int n,m,q,cnt,u,v,w,tot,x,k,dfn,id,btot;
int h[N],b[N],Fa[N<<1],a[N<<1],fa[N<<1][K],head[N<<1],l[N<<1],r[N<<1],rt[N<<1];
int ls[N*K],rs[N*K],sum[N*K];
struct edge{
    int u,v,w;
    edge(int uu=0,int vv=0,int ww=0){
        u=uu,v=vv,w=ww;
    }
}f[M];
struct Edge{
    int v,nxt;
}e[M<<1];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
bool Cmp(int a,int b){
    return a<b;
}
void add(int u,int v){
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
int getfa(int u){
    return u==Fa[u]?u:Fa[u]=getfa(Fa[u]);
}
void kruskal(){
    sort(f+1,f+m+1,cmp);
    for(int i=1;i<=n;++i) Fa[i]=i;
    tot=n;int count=0;
    for(int i=1;i<=m;++i){
        int u=f[i].u,v=f[i].v,w=f[i].w,uu=getfa(u),vv=getfa(v),p=0;
        if(uu!=vv){
            ++count;
            p=++tot,Fa[uu]=Fa[vv]=Fa[p]=p,a[p]=w;
            add(p,uu),add(uu,p),add(vv,p),add(p,vv);
        }
        if(count>=n-1) break;
    }
}
void change(int &now,int pre,int l,int r,int pos){
    now=++id;
    ls[now]=ls[pre],rs[now]=rs[pre],sum[now]=sum[pre]+1;
    if(l==r) return;
    int mid=l+r>>1;
    if(pos<=mid) change(ls[now],ls[pre],l,mid,pos);
    else change(rs[now],rs[pre],mid+1,r,pos);
}
int query(int pre,int nxt,int l,int r,int pos){
    int mid=l+r>>1,tmp=sum[ls[nxt]]-sum[ls[pre]];
    if(l==r) return l;  
    if(tmp>=pos) return query(ls[pre],ls[nxt],l,mid,pos);
    else return query(rs[pre],rs[nxt],mid+1,r,pos-tmp);
}
void dfs(int u,int p){
    fa[u][0]=p;
    for(int i=1;i<K;++i) fa[u][i]=fa[fa[u][i-1]][i-1];
    l[u]=dfn;
    int top=0;
    for(int i=head[u];~i;i=e[i].nxt){
        int v=e[i].v;
        if(v==p) continue;
        dfs(v,u);++top;
    }
    if(!top) ++dfn,change(rt[dfn],rt[dfn-1],1,btot,h[u]);
    r[u]=dfn;
} 
void lsh(){
    sort(b+1,b+n+1,Cmp);
    btot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i) h[i]=lower_bound(b+1,b+btot+1,h[i])-b; 
}
int main(){
    scanf("%d%d%d",&n,&m,&q);
    memset(head,-1,sizeof head),cnt=-1;
    for(int i=1;i<=n;++i) scanf("%d",&h[i]),b[i]=h[i];
    lsh();
    for(int i=1;i<=m;++i) scanf("%d%d%d",&u,&v,&w),f[i]=edge(u,v,w);
    kruskal();
    dfs(tot,0);
    for(int i=1;i<=q;++i){
        scanf("%d%d%d",&v,&x,&k);
        u=v;
        for(int j=K-1;j>=0;--j) if(fa[u][j] && a[fa[u][j]]<=x) u=fa[u][j];
        int tmp=sum[rt[r[u]]]-sum[rt[l[u]]],ans=0;
        if(tmp<k) printf("-1\n");
        else{
            ans=query(rt[l[u]],rt[r[u]],1,btot,tmp-k+1);
            printf("%d\n",b[ans]);  
        }
    }
    return 0;
}