kruskal重构树
kruskal重构树
Kruskal重构树
资料
模板
构建方法：初始时有 \(n\) 个叶子节点，运行 \(kruskal\) 最小生成树算法，对于用边权为 \(w\) 连接两个节点 \((u,v)\), 新建一个权值为 \(w\) 的节点 \(x\)，并连边 \((x,root(u))\) 和 \((x,root(v))\), 并将 \(x\) 置为这颗树的根节点。
这样建出来的其实是一个大根堆，可以用来求从点 \(x\) 出发只走边权 \(<=w\) 的边能到达的点的极大集合
做法就是从 \(x\) 倍增往上面跳直到点权 \(>w\)，设跳到的点为 \(u\)，那么 \(u\) 的所有叶子就是所求的极大集合
还有一个性质是：任意两个点路径上边权的最大值为它们的LCA的点权
例题
在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;
}