浅谈重构树

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

重构树

定义

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

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

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

一些性质

1. 重构树为一棵二叉树。
2. 有 n 个叶子节点，编号为 1 \sim n；有 n-1 个非叶子节点，编号为 n+1 \sim 2 \times n-1。
3. 拓扑序为 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;
}

我们可以给 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 满足：

1. b$ 的点权 $\le x
3. 在满足上述两个条件下，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;
}

::::