当前位置 博文首页 > liuchanglc：kruskal重构树学习笔记
按照 \(kruskal\) 算法的流程，把最小/大生成树中边权的关系映射到了一颗二叉树上
具体实现也很简单
在原本的 \(kruskal\) 算法中，每次查到两个不在同一集合的点，就新开一个节点
然后把两个节点的祖先节点分别向新节点连边，不计边权，但是要记录新点的点权，就是连接两个点的边的边权
新生成的树有以下特点
\(1\)、这棵树是一棵二叉树，且具有堆的性质。
\(2\)、树上除了叶子节点是原来的点，其余的点都是新建的点，且都有权值。
\(3\)、两个点 \(u\) 和 \(v\) 的 \(lca\) 的点权就对应着它们最小生成树上的路径上的最小/大值（瓶颈）
这样，我们就可以解决从某一个点出发，只能经过边权小于/大于 \(x\) 的边，在所有能到达的点中查询最值的问题
因为每遇到一个生成树上的边我们就会新开一个节点，所以节点数变为了原图的 \(2\) 倍
题目传送门
可以说是 \(kruskal\) 重构树的板子题
首先按照边权从大到小排序，构建 \(kruskal\) 重构树
这样，重构树就是一个小根堆
因为每次询问时海拔大于 \(a\) 的边都可以乘车通过
所以我们肯定要在 \(v\) 能乘车到达的点中选择到 \(1\) 的最短路最短的点
在重构树上，我们只需要维护一个倍增数组
查询时倍增跳到第一个深度小于等于 \(a\) 的祖先节点
这个节点的子树中的所有点一定可以由 \(x\) 乘车到达
只要在这棵子树中查询到 \(1\) 的最短路的最小值就行了
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int h[maxn],tot=1,n,m,q,k,s,t,dis[maxn],cnt,fa[maxn],val[maxn];
struct Node{
int zb,yb,val;
Node(){}
Node(rg int aa,rg int bb,rg int cc){
zb=aa,yb=bb,val=cc;
}
}jl[maxn];
bool cmp(rg Node aa,rg Node bb){
return aa.val>bb.val;
}
int zhao(rg int xx){
if(xx==fa[xx]) return xx;
return fa[xx]=zhao(fa[xx]);
}
struct asd{
int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
bool vis[maxn];
struct jie{
int num,jl;
jie(){}
jie(rg int aa,rg int bb){
num=aa,jl=bb;
}
bool operator <(const jie& A)const{
return jl>A.jl;
}
};
void dij(){
std::priority_queue<jie> Q;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
Q.push(jie(1,0));
while(!Q.empty()){
rg int now=Q.top().num;
Q.pop();
if(vis[now]) continue;
vis[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(dis[u]>dis[now]+b[i].val){
dis[u]=dis[now]+b[i].val;
Q.push(jie(u,dis[u]));
}
}
}
}
int dep[maxn],mindis[maxn],zx[maxn][22],mmin[maxn][22];
std::vector<int> g[maxn];
void dfs(rg int now,rg int lat){
dep[now]=dep[lat]+1;
mindis[now]=dis[now];
mmin[now][0]=val[lat];
zx[now][0]=lat;
for(rg int i=1;(1<<i)<=dep[now];i++){
zx[now][i]=zx[zx[now][i-1]][i-1];
mmin[now][i]=std::min(mmin[now][i-1],mmin[zx[now][i-1]][i-1]);
}
for(rg int i=0;i<g[now].size();i++){
rg int u=g[now][i];
dfs(u,now);
mindis[now]=std::min(mindis[now],mindis[u]);
}
}
int latans;
int solve(rg int now,rg int val){
for(rg int i=20;i>=0;i--){
if(mmin[now][i]>val){
now=zx[now][i];
}
}
return mindis[now];
}
int main(){
t=read();
while(t--){
memset(dep,0,sizeof(dep));
memset(h,-1,sizeof(h));
memset(mmin,0,sizeof(mmin));
memset(zx,0,sizeof(zx));
tot=1,latans=0;
n=read(),m=read();
rg int aa,bb,cc,dd;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),cc=read(),dd=read();
jl[i]=Node(aa,bb,dd);
ad(aa,bb,cc),ad(bb,aa,cc);
}
dij();
cnt=n;
std::sort(jl+1,jl+m+1,cmp);
for(rg int i=1;i<=n+n;i++) fa[i]=i;
for(rg int i=1;i<=n+n;i++) g[i].clear();
for(rg int i=1;i<=m;i++){
aa=jl[i].zb,bb=jl[i].yb,cc=jl[i].val;
aa=zhao(aa),bb=zhao(bb);
if(aa==bb) continue;
val[++cnt]=cc;
fa[aa]=fa[bb]=cnt;
g[cnt].push_back(aa),g[cnt].push_back(bb);
}
dfs(cnt,0);
q=read(),k=read(),s=read();
for(rg int i=1;i<=q;i++){
aa=read(),bb=read();
aa=(aa+k*latans-1)%n+1;
bb=(bb+k*latans)%(s+1);
printf("%d\n",latans=solve(aa,bb));
}
}
return 0;
}
题目传送门
还是 \(kruskal\) 重构树的板子题
按照边权从小到大排序构建重构树
查询的时候只需要在祖先节点对应的主席树里查询 \(k\) 大就行了
因为只有询问子树的操作，所以可以按照 \(dfn\) 序进行处理
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=4e5+5,maxm=5e5+5;
int h[maxn],tot=1,fa[maxn],n,m,q,val[maxn],cnt,hig[maxn];
struct Node{
int zb,yb,val;
Node(){}
Node(rg int aa,rg int bb,rg int cc){
zb=aa,yb=bb,val=cc;
}
}jl[maxm];
bool cmp(rg Node aa,rg Node bb){
return aa.val<bb.val;
}
struct asd{
int to,nxt;
}b[maxn<<1];
void ad(rg int aa,rg int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int zhao(rg int xx){
if(xx==fa[xx]) return xx;
return fa[xx]=zhao(fa[xx]);
}
int zx[maxn][22],mmax[maxn][22],dep[maxn],rt[maxn],rtcnt;
struct trr{
int lch,rch,siz;
}tr[maxn*50];
int ad(rg int da,rg int pre,rg int l,rg int r,rg int wz){
da=++rtcnt;
tr[da]=tr[pre];
tr[da].siz++;
if(l==r) return da;
rg int mids=(l+r)>>1;
if(wz<=mids) tr[da].lch=ad(tr[da].lch,tr[pre].lch,l,mids,wz);
else tr[da].rch=ad(tr[da].rch,tr[pre].rch,mids+1,r,wz);
return da;
}
int cx(rg int da,rg int pre,rg int l,rg int r,rg int kth){
if(l==r) return l;
rg int mids=(l+r)>>1,nsiz=tr[tr[da].rch].siz-tr[tr[pre].rch].siz;
if(nsiz>=kth) return cx(tr[da].rch,tr[pre].rch,mids+1,r,kth);
else return cx(tr[da].lch,tr[pre].lch,l,mids,kth-nsiz);
}
int getlca(rg int xx,rg int yy){
if(dep[xx]<dep[yy]) std::swap(xx,yy);
rg int len=dep[xx]-dep[yy],k=0;
while(len){
if(len&1) xx=zx[xx][k];
k++,len>>=1;
}
if(xx==yy) return xx;
for(rg int i=20;i>=0;i--){
if(zx[xx][i]!=zx[yy][i]){
xx=zx[xx][i],yy=zx[yy][i];
}
}
return zx[xx][0];
}
int dfn[maxn],dfnc,siz[maxn],rk[maxn],sta[maxn],tp;
void dfs(rg int now,rg int lat){
dep[now]=dep[lat]+1;
zx[now][0]=lat;
mmax[now][0]=val[lat];
dfn[now]=++dfnc;
rk[dfnc]=now;
siz[now]=1;
for(rg int i=1;(1<<i)<=dep[now];i++){
zx[now][i]=zx[zx[now][i-1]][i-1];
mmax[now][i]=std::max(mmax[now][i-1],mmax[zx[now][i-1]][i-1]);
}
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs(u,now);
siz[now]+=siz[u];
}
}
int zhao(rg int now,rg int val){
for(rg int i=20;i>=0;i--){
if(mmax[now][i]<=val && zx[now][i]){
now=zx[now][i];
}
}
return now;
}
int solve(rg int xx,rg int yy,rg int kth){
rg int lca=zhao(xx,yy);
if(tr[rt[dfn[lca]+siz[lca]-1]].siz-tr[rt[dfn[lca]-1]].siz<kth) return -1;
return sta[cx(rt[dfn[lca]+siz[lca]-1],rt[dfn[lca]-1],1,tp,kth)];
}
int main(){
memset(mmax,0x3f,sizeof(mmax));
memset(h,-1,sizeof(h));
n=read(),m=read(),q=read();
for(rg int i=1;i<=n;i++) hig[i]=read();
for(rg int i=1;i<=n;i++) sta[++tp]=hig[i];
std::sort(sta+1,sta+1+tp);
tp=std::unique(sta+1,sta+1+tp)-sta-1;
for(rg int i=1;i<=n;i++) hig[i]=std::lower_bound(sta+1,sta+1+tp,hig[i])-sta;
cnt=n;
rg int aa,bb,cc;
for(rg int i=1;i<=m;i++){
aa=read(),bb=read(),cc=read();
jl[i]=Node(aa,bb,cc);
}
std::sort(jl+1,jl+1+m,cmp);
for(rg int i=1;i<=n+n;i++) fa[i]=i;
for(rg int i=1;i<=m;i++){
aa=jl[i].zb,bb=jl[i].yb,cc=jl[i].val;
aa=zhao(aa),bb=zhao(bb);
if(aa==bb) continue;
val[++cnt]=cc;
fa[aa]=cnt,fa[bb]=cnt;
ad(aa,cnt),ad(cnt,aa);
ad(bb,cnt),ad(cnt,bb);
}
for(rg int i=1;i<=cnt;i++){
if(fa[i]==i){
dfs(i,0);
}
}
for(rg int i=1;i<=cnt;i++){
rt[i]=rt[i-1];
if(rk[i]<=n){
rt[i]=ad(rt[i],rt[i],1,tp,hig[rk[i]]);
}
}
for(rg int i=1;i<=q;i++){
aa=read(),bb=read(),cc=read();
printf("%d\n",solve(aa,bb,cc));
}
return 0;
}
