克鲁斯卡尔重构树略解

Dispwnl

2018-08-25 08:42:04

Algo. & Theory

惊了百度词条还是没有收录

先看一道题：

给你一个图，每次询问给定一个位置、长度和k，问从这个点出发，只能经过不大于这个长度的边，到达的点中点权第k大的点权

数据是10w级别的

显然是先构造最小生成树，但是没法根据询问长度进行修改

如果允许离线呢？

可以把询问按长度排序，每次把不大于这个长度的边加入最小生成树，然后对每个联通块建主席树，加边合并主席树

布星现在是强制在线

这就需要用到克鲁斯卡尔重构树

比如这个图：

ta的最小生成树是这样：

在连接两个联通块的时候，我们新建一个节点，与两个联通块的代表点相连，然后这个新建节点成为这个联通块的代表点，这个点的点权为这条边的长度

最后形成的图：

可以发现，把原来的边去掉，新建点与原来的点是在一棵树里的，把这棵树提出来

发现每个节点的权值肯定大于等于ta子树中任意一个点的权值，因为构造最小生成树的时候越大的边出现的越晚，对应建立的点深度也越浅

所以每个点对应子树里都是边长小于等于ta的点权的联通块

还是刚才那个问题，可以发现对于每个询问，我们需要找一个点：

然后答案肯定在ta的子树中，只需要考虑子树，所以对这棵树的dfs序建立主席树，在子树里找k大点就行了

怎么找这个点呢？由上面的性质可以知道，点权越大，子树越大

所以我们只用找询问给定点的祖先里点权不大于给定长度的最大的点，这个可以用倍增实现

这样问题就解决啦

离线部分代码（合并主席树）

int merge(int k,int y)//合并部分，对应相加
{
    if(!k) return y;
    if(!y) return k;
    if(!tl&&!tr) s[k].x+=s[y].x;
    else tl=merge(tl,s[y].l),tr=merge(tr,s[y].r),s[k].x=s[tl].x+s[tr].x;
    return k;
}
int ask(int l,int r,int k,int x)//查询部分
{
    if(l>=r) return l;
    if(x<=s[tl].x) return ask(l,mid,tl,x);
    else return ask(mid+1,r,tr,x-s[tl].x);
}
int main()
{
    ...//输入+处理部分...
    int l=1,num=0;
    for(int i=1;i<=q;++i)
      {
        int v=qu[i].v,x=qu[i].x,k=qu[i].k;
        for(;l<=m&&qu[i].x>=c[l].dis;++l)
          {
            if(num==n-1) break;
            int r1=find(c[l].x),r2=find(c[l].y);
            if(r1==r2) continue;
            ++num;
            if(siz[r1]>siz[r2]) fa[r2]=r1,rt[r1]=merge(rt[r1],rt[r2]),siz[r1]+=siz[r2];
            else fa[r1]=r2,rt[r2]=merge(rt[r2],rt[r1]),siz[r2]+=siz[r1];//启发式合并
          }
        v=rt[find(v)];
        if(s[v].x<k) ans[qu[i].id]=-1;//不到k个就-1
        else ans[qu[i].id]=ID[ask(1,id,v,s[v].x-k+1)];
      }
    for(int i=1;i<=q;++i)
      printf("%d\n",ans[i]);
    return 0;
}

在线部分代码

int ASK(int pos,int x,int k)//处理询问
{
    for(int i=20;i>=0;--i)
      if(f[i][pos]&&v[f[i][pos]]<=x) pos=f[i][pos];//倍增查询
    int r1=rt[id_l[pos]],r2=rt[id_r[pos]];//找到子树dfs序范围
    if(s[r2].x-s[r1].x<k) return -1;//没有k个点就返回-1
    return ID[ask(r2,r1,1,id,s[r2].x-s[r1].x-k+1)];//主席树查询，ID是离散化编号对应点权值
}
void dfs(int x)//处理dfs序
{
    use[x]=1,Id[++Tot]=x;
    for(int i=h[x];i;i=cc[i].x)
      dfs(cc[i].y);
    if(x>n) Id[++Tot]=x;//dfs序，因为>n的主席树与前面<=n的树合并，所有要子树最右边dfs序应该是>n的点
}
int main()
{
    ...//输入相关...
    int num=0,ans=0;
    for(int i=1;i<=m;++i)
      {
        if(num==n-1) break;
        int r1=find(c[i].x),r2=find(c[i].y);
        if(r1==r2) continue;
        ++num,fa[++cnt]=cnt,f[0][r1]=f[0][r2]=cnt,v[cnt]=c[i].dis,fa[r1]=fa[r2]=cnt;//cnt表示新建点编号，注意应该从n开始编号
        add(cnt,r1),add(cnt,r2);//从cnt向r1,r2连边
      }//建树
    for(int i=1;i<=n;++i)
      if(!use[i]) dfs(find(i));//dfs序
    for(int i=1;i<=Tot;++i)
      {
        int tt=Id[i];
        if(tt<=n) rt[i]=change(rt[i-1],1,id,b[tt]);//dfs序建主席树
        else
        {
            rt[i]=rt[i-1];//如果是新建节点，根就连到原来节点上（因为没有题目查询需要的点权）
            if(!id_l[tt]) id_l[tt]=i;
            else id_r[tt]=i;
        }
      }
    for(int j=1;j<=20;++j)
      for(int i=1;i<=cnt;++i)
        f[j][i]=f[j-1][f[j-1][i]];//倍增
    for(int i=1;i<=q;++i)
      {
        if(ans==-1) ans=0;
        int v=read()^ans,x=read()^ans,k=read()^ans;
        printf("%d\n",ans=ASK(v,x,k));
      }
}

瞬间字数就多了

NOI2018 D1T1也是一道重构树的模板题，建立海拔的最大生成树，对于每个点到1号节点的最短路长度查询即可