Kruskal 重构树

· · 算法·理论

Kruskal 重构树

可以求解图上两点简单路径上边长的最大值。

考虑 Kruskal 求最小生成树的过程。她丢失了 “每次被选择的是哪条边，对应哪两个顶点” 这一个信息。这个信息包含单调性，是非常好的性质。我们希望能得到她。

考虑如何在求出最小生成树的过程中，保留这个信息。

当我们需要在 u,v 之间连一条权值为 w 的边时：

其余过程直接套用 \text{Kruskal} 。

这样得到一棵树就是重构树。每个叶子就代表原图中的节点，每个非叶节点就代表最小生成树上的一条边。

重构树的根应该为 2n-1，也就是最后一个点。因为如果以 1\sim n 中的任何一个点作为根会破坏重构树的形态；连边时向下连边，只有以 2n-1 为根时才能遍历整棵树。

动态 DP 问题是猫锟在 WC2018 讲的黑科技，一般用来解决树上的带有点权（边权）修改操作的 DP 问题。根据以上性质，她启发我们动态 DP 可以运用在重构树上很好地。

值得注意的是，从叶子开始，向上每一层的点权都是单调的。增减性由最大生成树还是最小决定。

我们把边按照权值从小到大排序，那么对于所有非叶子节点，它的点权（原图的边权）一定不大于父亲节点的点权，所以路径上的最大值即为 \text{LCA} 的点权。原树 u 到 v 路径上的边权最大值为重构树上 u 和 v 的 \text{LCA} 的点权。

注意：树上多个点的 LCA，就是 DFS 序最小的和 DFS 序最大的这两个点的 LCA。

[bzoj 3274]

给你 n 个点 m 条边的无向图，每条边的长度为 d_i。现在有 k 个询问 ，每次询问 u,v 之间的所有路径中，最长边的最小值是多少？1\le n\le 1.5\times 10^4，1\le m\le 3\times 10^4，1\le k\le 2\times 10^4，1\le d_i\le 10^9

考虑建立 Kruskal 重构树。

为什么要取得最小生成树呢？因为最小边一定会在最小生成树上。符合了题目条件。

其实直接在最小生成树上倍增就可以了。但是我们考虑使用重构树的性质来做。

发现直接求得两点 \text{LCA} 对应的点权即可。

[NOI 2018] 归程

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图（节点的编号从 1 至 n）。我们依次用 l,a 描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。Yazid 的家恰好在魔力之都的 1 号节点。对于接下来 Q 天，每一天 Yazid 都会告诉你他的出发点 v ，以及当天的水位线 p。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：

  • 车会在新的出发点被准备好。
  • Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

强制在线。

n\leq2\times10^5\ m,q\leq4\times10^5

我们希望找到一条路 v\to u\to 1 。其中满足 v\to u 可达并且在这个条件下 u\to 1 最短路最短。

先预处理出 1 到其他顶点的最短路。

贪心地，建出原图关于海拔高度的最大生成树。

当前询问选中节点 v ，她在树上的深度是 \rm{dep}_v 。特别的，根节点的深度是 0 。

通过树上倍增，求得小于等于 当前的积水深度 的海拔高度对应的最浅顶点 k 。深度为 \rm{dep}_k 。

这个顶点子树往下的所有顶点都满足 v\to u 可达。

如果 v 不在子树内，直接考虑最短路即可。

否则，子树内的所有叶子节点都是 v\to u 可达的。找到子树内叶子的最短路的最小值即可。

这个过程可以通过树上 dp 实现。但是根据树的性质我们发现不用每次都 dfs。取 min 的过程直接在建立重构树的过程中实现。

ll n,m,u,v,l,a,Q,K,S,fa[N],f[N][21],eat[N];

struct kruskal{
    ll u,v,high;
}tr[N];

bool cmp(kruskal a,kruskal b){
    return a.high>b.high;
}

ll find(ll x){
    if(x==fa[x]) return fa[x];
    return fa[x]=find(fa[x]);
}

ll dis[N],frm[N],cnt=0,vis[N];
struct edge{ll to,val,net;}e[N];
void add(ll x,ll y,ll z){e[++cnt]={y,z,frm[x]};frm[x]=cnt;}
void ADD(ll x,ll y,ll z){add(x,y,z);add(y,x,z);}

void dijkstra(ll s){
    priority_queue<frac>q;
    for(int i=1;i<=n;i++) dis[i]=1e12,vis[i]=0;dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        ll cur=q.top().second;q.pop();
        if(vis[cur]) continue;vis[cur]=1;
        for(int i=frm[cur];i;i=e[i].net){
            ll x=e[i].to;
            if(dis[x]>dis[cur]+e[i].val) 
                dis[x]=dis[cur]+e[i].val,
                q.push(make_pair(-dis[x],x));
        }
    }
}

void rebuild(){
    sort(tr+1,tr+m+1,cmp);
    ll getin=0,index=n;
    for(int i=1;i<=2*n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        if(getin==n-1) break;
        ll x=find(tr[i].u),y=find(tr[i].v);
    //  ll x=find(tr[i].u),y=tr[i].v; 笑点解析
        if(x==y) continue;
        fa[x]=fa[y]=++index;eat[index]=tr[i].high;
        dis[index]=min(dis[x],dis[y]);
        f[x][0]=f[y][0]=index;
        getin++;
    }
    for(int j=1;(1<<j)<=index;j++)
        for(int i=1;i<=index;i++)
            f[i][j]=f[f[i][j-1]][j-1];
}

ll query(ll u,ll p){
    for(int i=19;i>=0;i--)
        if(f[u][i]&&eat[f[u][i]]>p) 
            u=f[u][i];
    return dis[u];
}

void solve(){
    n=read();m=read();
    for(int i=1;i<=m;i++){
        u=read();v=read();l=read();a=read();
        ADD(u,v,l);
        tr[i]={u,v,a};
    }
    dijkstra(1);
    rebuild();
    Q=read();K=read();S=read();
    ll lastans=0;
    while(Q-->0){
        ll v=read(),p=read();
        v=(v+K*lastans-1)%n+1;
        p=(p+K*lastans)%(S+1);
        lastans=query(v,p);
        cout<<lastans<<"\n";
    }
    for(int i=1;i<=cnt;i++) e[i]={0,0,0};cnt=0;
    for(int i=1;i<=n;i++) frm[i]=0;
    for(int i=1;i<=2*n;i++)for(int j=0;j<=19;j++)[i][j]=0;
    for(int i=1;i<=m;i++) tr[i]={0,0,0};
}

CF1706E

给出 n个点， m 条边的不带权连通无向图， q 次询问至少要加完编号前多少的边，才能使得 [l,r] 中的所有点两两连通。

就是每一对点都要两两连通。考虑到上文 LCA 部分的 注意 ，结合重构树关于 LCA 的性质就做完了。