浅谈重构树

chenhanzheapple · 2025-09-07 21:58:02 · 算法·理论

重构树

定义

现有 n 个集合，每次合并两个集合，合并 n-1 次后就会变为一个大集合。

将集合合并的过程如下图所示方式记录，就构成了一棵重构树。

再给出一棵完整的重构树作为例子：

一些性质

重构树为一棵二叉树。
有 n 个叶子节点，编号为 1 \sim n；有 n-1 个非叶子节点，编号为 n+1 \sim 2 \times n-1。
拓扑序为 2 \times n-1,2 \times n-2,\dots,2,1。

例题：ABC314F A Certain Game

给你 n 个人，初始每个人是单独的一个队伍。现在举行了 n-1 场比赛，第 i 场比赛由第 p_i 个选手的所在的队伍为先手，第 q_i 个选手所在的队伍为后手。设先手有 a 人，后手有 b 人，则先手获胜概率为 \frac{a}{a+b}，后手获胜概率为 \frac{b}{a+b}。比赛完成后，两个队伍合并成一个。求最终每个选手的获胜概率。

使用并查集构建重构树。

每次比赛新建一个节点，合并这两只队伍的获胜期望到这个新建的节点上，记录新节点的左右儿子，最后使用性质 3 统计答案即可（可以不用性质 3，做一遍 DFS，但更为冗长）。

代码：

cnt = n;
for(int i=1;i<=n;i++){
    fa[i] = i,sz[i] = 1;
}
for(int i=1;i<n;i++){
    int p,q;
    cin >> p >> q;
    p = find(p),q = find(q);
    sz[++cnt] = sz[p]+sz[q];
    f[p] = sz[p]*fast_pow(sz[cnt],MOD-2)%MOD;
    f[q] = sz[q]*fast_pow(sz[cnt],MOD-2)%MOD;
    l[cnt] = p,r[cnt] = q;
    fa[p] = fa[q] = fa[cnt] = cnt;
}
for(int i=2*n-1;i>=n+1;i--){
    f[l[i]] = (f[l[i]]+f[i])%MOD;
    f[r[i]] = (f[r[i]]+f[i])%MOD;
}

# 构建表达式树基本同上。若该表达式的后缀表达式为 `x1 ! x2 x4 | x3 x5 ! & & ! &`，则构建的表达式树为： ![](https://cdn.luogu.com.cn/upload/image_hosting/nxtmeoqj.png) # Kruskal 重构树 ## 定义前置芝士：最小生成树 Kruskal 算法。注意到在跑 Kruskal 的时候，每次会按边权从小到大贪心选边，若该边的两端不在同一个连通块内，就将这两个连通块合并。把这个合并的过程建成一棵重构树，就是 Kruskal 重构树。对于下图： ![](https://oi-wiki.org/graph/images/mst5.png) 这张图的 Kruskal 重构树为： ![](https://oi-wiki.org/graph/images/mst6.png) ## 一些性质 ### 性质 $1

我们可以给 Kruskal 重构树上的每一个点钦定一个点权。对于非叶子结点，它的点权为合并时的对应边权，叶子结点的点权为负无穷（若是最大生成树，为正无穷）。显然 Kruskal 重构树是一个大根堆（若是最大生成树，为小根堆）。

该性质是 Kruskal 重构树其他性质的基础。

性质 2

在原图中，a 到 b 的所有简单路径上最大边权的最小值为最小生成树上 a 到 b 路径上边权的最大值，即 Kruskal 重构树的上 lca(a,b) 的点权。

基于这个性质，我们可以完成一些题目。

::::info[P1967 [NOIP 2013 提高组] 货车运输] 这道题只是将性质 2 转化了一下，变为所有简单路径上最小边权的最大值，因此建树时要建最大生成树。

所以直接构建 Kruskal 重构树，求出点权，对于每次询问求 LCA 即可。 ::::

性质 3

原图中，从点 a 出发，仅经过边权 \le x 的边能到的点集为 Kruskal 重构树上 b 子树的所有叶子，其中 b 满足：

b$ 的点权 $\le x
在满足上述两个条件下，b 的深度最小。

例题： ::::info[P4768 [NOI2018] 归程] 每一天，鸭子德要先开一段经过边权 \le p 的车到 x，然后从 x 走到 1。

对于每一天开车能到的点集 X，可以直接建最大生成树的 Kruskal 重构树，然后利用性质 3 求出 X，每次询问的答案即为 \min_{x \in X} dis_x，其中 dis_x 为点 x 到 1 的最短路，可以使用 dijkstra 预处理。

首先建好 Kruskal 重构树，然后预处理最短路和 Kruskal 重构树上每个点子树点权的最小值。

对于每次询问，倍增找到 b，输出 b 子树的点权最小值即可。

时间复杂度：O(q \log n)。

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int t,n,m,cnt;
struct node{
    int x,w,y;
};
struct edge{
    int x,y,l,a;
}e[400005];
struct node2{
    int x,w;
    bool operator < (const node2 &x)const{
        return x.w<w;
    }
};
int dis[400005],p[400005],val[400005],fa[400005],f[400005][20],l[400005],r[400005],de[400005];
bool vis[400005];
vector<node> v[400005];
void dijkstra(int s){
    priority_queue<node2> que;
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s] = 0;
    que.push((node2){s,0});
    while(!que.empty()){
        auto t = que.top();
        que.pop();
        if(vis[t.x]){
            continue;
        }
        vis[t.x] = 1;
        for(auto x:v[t.x]){
            if(dis[t.x]+x.w<dis[x.x]){
                dis[x.x] = dis[t.x]+x.w;
                que.push((node2){x.x,dis[x.x]});
            }
        }
    }
}
bool cmp(edge x,edge y){
    return x.a>y.a;
}
int find(int x){
    return p[x]==x ? x : p[x] = find(p[x]);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--){
        memset(val,0,sizeof(val));
        memset(l,-1,sizeof(l));
        memset(r,-1,sizeof(r));
        cin >> n >> m;
        cnt = n;
        for(int i=1;i<=n;i++){
            p[i] = i;
            v[i].clear();
        }
        for(int i=1;i<=m;i++){
            int x,y,w,h;
            cin >> x >> y >> w >> h;
            v[x].push_back((node){y,w,h});
            v[y].push_back((node){x,w,h});
            e[i] = {x,y,w,h};
        }
        dijkstra(1);
        sort(e+1,e+m+1,cmp);
        int tot = 0;
        for(int i=1;i<=m;i++){
            int x = find(e[i].x),y = find(e[i].y),w = e[i].a;
            if(x!=y){
                val[++cnt] = w;
                fa[x] = fa[y] = cnt;
                l[cnt] = x,r[cnt] = y;
                p[x] = p[y] = p[cnt] = cnt;
                tot++;
                if(tot==n-1){
                    break;
                }
            }
        }
        for(int i=1;i<=cnt;i++){
            f[i][0] = fa[i];
        }
        for(int j=1;j<=19;j++){
            for(int i=1;i<=cnt;i++){
                f[i][j] = f[f[i][j-1]][j-1];
            }
        }
        memset(de,0,sizeof(de));
        for(int i=n+1;i<=cnt;i++){
            dis[i] = min(dis[l[i]],dis[r[i]]);
            // de[i] = de[l[i]]+1;
        }
        de[cnt] = 1;
        for(int i=cnt;i>=n+1;i--){
            de[l[i]] = de[r[i]] = de[i]+1;
        }
        int lastans = 0,q,k,s;
        cin >> q >> k >> s;
        while(q--){
            int x,y;
            cin >> x >> y;
            x = (x+k*lastans-1)%n+1;
            y = (y+k*lastans)%(s+1);
            for(int i=19;i>=0;i--){
                if(de[x]-(1<<i)>0 && val[f[x][i]]>y){
                    x = f[x][i];
                }
            }
            cout << (lastans = dis[x]) << endl;
        }
    }
    return 0;
}

::::

拓展： ::::info[P7834 [ONTAK2010] Peaks 加强版]

~~似乎并非浅谈~~

前置知识：可持久化线段树

发现把归程的第二问换成了可达性第 k 大（之前因为看成了第 k 小调了很久……）。

因为仅经过边权 \le x 的边能到的点集为 Kruskal 重构树上 b 子树的权值第 k 大（叶子权值为原值，非叶子为 0，统计时排除所有 0），在同一个子树内的信息容易想到转化为 dfs 序处理，因此在 Kruskal 重构树的 dfs 序上做静态区间第 k 大，用可持久化线段树维护即可。

当然也可以用线段树合并做，这里不给出示例了。

代码：

#include<bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
int n,m,q,cnt = 1,cntt,tot,tott;
struct edge{
    int x,y,w;
}e[1000005];
int p[400005],fa[400005],l[400005],r[400005],val[12800005],tmp[400005],b[400005],root[400005],dfn[400005],endd[400005],vall[400005],f[400005][20],s[400005];
struct node{
    int l,r;
}tree[12800005];
int copy(int x){
    int y = ++cnt;
    tree[y] = tree[x];
    val[y] = val[x]+1;
    return y;
}
void build(int x,int l,int r){
    if(l==r){
        return;
    }
    int mid = (l+r)/2;
    tree[x].l = ++cnt;
    build(cnt,l,mid);
    tree[x].r = ++cnt;
    build(cnt,mid+1,r);
}
int query(int x,int y,int l,int r,int a){
    if(l==r){
        return l;
    }
    int mid = (l+r)/2,res = 0;
    if(a<=val[tree[x].r]-val[tree[y].r]){
        return query(tree[x].r,tree[y].r,mid+1,r,a);
    }
    return query(tree[x].l,tree[y].l,l,mid,a-val[tree[x].r]+val[tree[y].r]);
}
int modify(int x,int l,int r,int a){
    x = copy(x);
    if(l==r){
        return x;
    }
    int mid = (l+r)/2;
    if(a<=mid){
        tree[x].l = modify(tree[x].l,l,mid,a);
        return x;
    }
    tree[x].r = modify(tree[x].r,mid+1,r,a);
    return x;
}
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int find(int x){
    return p[x]==x ? x : p[x] = find(p[x]);
}
void dfs(int x){
    if(x==-1){
        return;
    }
    dfn[x] = ++cntt;
    s[cntt] = tmp[x];
    dfs(l[x]);
    dfs(r[x]);
    endd[x] = cntt;
}
void kruskal(){
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(r));
    for(int i=1;i<=n;i++){
        p[i] = i;
    }
    sort(e+1,e+m+1,cmp);
    tot = n,tott = 0;
    for(int i=1;i<=m;i++){
        int x = find(e[i].x),y = find(e[i].y),w = e[i].w;
        if(x!=y){
            vall[++tot] = w;
            fa[x] = fa[y] = tot;
            l[tot] = x,r[tot] = y;
            p[x] = p[y] = p[tot] = tot;
            tott++;
            if(tott==n-1){
                break;
            }
        }
    }
    for(int i=1;i<=tot;i++){
        f[i][0] = fa[i];
    }
    for(int j=1;j<=19;j++){
        for(int i=1;i<=tot;i++){
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
    for(int i=1;i<=tot;i++){
        if(p[i]==i){
            dfs(i);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++){
        cin >> tmp[i];
        b[i] = tmp[i];
    }
    sort(b+1,b+n+1);
    int mm = unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++){
        tmp[i] = lower_bound(b+1,b+mm+1,tmp[i])-b;
    }
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin >> x >> y >> w;
        e[i] = {x,y,w};
    }
    vall[0] = 1e18;
    kruskal();
    build(root[0] = 1,1,mm);
    for(int i=1;i<=tot;i++){
        if(s[i]){
            root[i] = modify(root[i-1],1,mm,s[i]);
        }
        else{
            root[i] = root[i-1];
        }
    }
    int lastans = 0;
    while(q--){
        int u,x,k;
        cin >> u >> x >> k;
        u = (u^lastans)%n+1,x^=lastans,k = (k^lastans)%n+1;
        for(int i=19;i>=0;i--){
            if(f[u][i] && vall[f[u][i]]<=x){
                u = f[u][i];
            }
        }
        if(val[root[endd[u]]]-val[root[dfn[u]-1]]<k){
            cout << -1 << endl;
            lastans = 0;
            continue;
        }
        int ans = b[query(root[endd[u]],root[dfn[u]-1],1,mm,k)];
        lastans = ans;
        cout << (ans ? ans : -1) << endl;
    }
    return 0;
}

::::