Kruskal重构树

资料

Kruskal重构树入门 自为风月马前卒

模板

构建方法：初始时有 $n$ 个叶子节点，运行 $kruskal$ 最小生成树算法，对于用边权为 $w$ 连接两个节点 $(u,v)$, 新建一个权值为 $w$ 的节点 $x$，并连边 $(x,root(u))$ 和 $(x,root(v))$, 并将 $x$ 置为这颗树的根节点。

这样建出来的其实是一个大根堆，可以用来求从点 $x$ 出发只走边权 $<=w$ 的边能到达的点的极大集合

做法就是从 $x$ 倍增往上面跳直到点权 $>w$，设跳到的点为 $u$，那么 $u$ 的所有叶子就是所求的极大集合

还有一个性质是：任意两个点路径上边权的最大值为它们的LCA的点权

例题

Peaks加强版

在Bytemountains有N座山峰，每座山峰有他的高度hi。

有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走.

现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出−1

kruskal重构树 + 主席树

vector<int> X;
EDGE(MAXN,MAXN*2);
int n,m,q,cnt,last=-1;
int h[MAXN],a[MAXN],b[MAXN],fa[MAXN],st[MAXN],ed[MAXN],f[MAXN][21];
struct temp{int u,v,w;}edg[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int u,int fa)
{
    st[u]=++cnt,b[cnt]=h[u],f[u][0]=fa;
    go(u)if(v!=fa)dfs(v,u);
    ed[u]=cnt;
}
int root[MAXN],s[MAXN*10],ls[MAXN*10],rs[MAXN*10],cnt_;
void update(int pre,int &rt,int l,int r,int pos)
{
    if(!rt)rt=++cnt_; s[rt]=s[pre]+1; if(l==r)return;
    if(pos<=mid)update(ls[pre],ls[rt],l,mid,pos),rs[rt]=rs[pre];
    else update(rs[pre],rs[rt],mid+1,r,pos),ls[rt]=ls[pre];
}
void query(int pre,int rt,int l,int r,int k)
{
    if(l==r){printf("%d\n",X[l-1]),last=X[l-1];return;}
    int sum=s[rs[rt]]-s[rs[pre]];
    if(sum>=k)query(rs[pre],rs[rt],mid+1,r,k);
    else query(ls[pre],ls[rt],l,mid,k-sum);
}
bool cmp(const temp &a,const temp &b){return a.w<b.w;}
int work()
{
    scanf("%d%d%d",&n,&m,&q);
    fp(i,1,n)scanf("%d",&h[i]),X.pb(h[i]); sort(all(X)),unq(X);
    fp(i,1,n)h[i]=lb(all(X),h[i])-X.begin()+1;
    fp(i,1,2*n)fa[i]=i;
    fp(i,1,m)scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].w);
    sort(edg+1,edg+1+m,cmp);
    fp(i,1,m)if(find(edg[i].u)!=find(edg[i].v))
    {
        a[++n]=edg[i].w; int fu=find(edg[i].u),fv=find(edg[i].v);
        addedge(n,fu),addedge(n,fv),fa[fu]=fa[fv]=n;
    }
    fp(i,1,n)if(!st[i])dfs(find(i),0);
    fp(j,1,20)fp(i,1,n)f[i][j]=f[f[i][j-1]][j-1];
    fp(i,1,n)
        if(b[i])update(root[i-1],root[i],1,X.size(),b[i]);
        else root[i]=root[i-1];
    while(q--)
    {
        int u,x,k;scanf("%d%d%d",&u,&x,&k);
        if(last!=-1)u^=last,x^=last,k^=last;
        fd(i,20,0)if(f[u][i]&&a[f[u][i]]<=x)u=f[u][i];
        int l=st[u],r=ed[u];
        if(s[root[r]]-s[root[l-1]]<k)printf("-1\n"),last=-1;
        else query(root[l-1],root[r],1,X.size(),k);
    }
    return 0;
}