Kruskal 重构树

akakal · 2025-09-11 10:34:45 · 算法·理论

题单：https://www.luogu.com.cn/training/874986。

算法讲解

Kruskal 重构树的点集由 Kurskal 最小/大生成树的 n-1 个边权和 n 个点构成。

定义三元组 (x,y,z) 表示 x 和 y 之间有一条边权为 z 的边。

在生成树的时候，进行如下操作重构：

• 给定 (x,y,z)；
• 此时 f_x,f_y 作为 x,y 在并查集中的根，本质是 Kurskal 重构树中 x,y 的深度最小的祖先；
• 若 f_x\ne f_y，则 cnt 自增，新建结点 cnt，令 f_{f_x}=f_{f_y}=cnt，且 val_{cnt}\leftarrow z；
• 当 cnt=2n-1 时，停止生成和重构。

Kruskal 重构树满足以下性质：

• 是一棵二叉树，满足所有叶子结点为原图中的结点，所有非叶子结点为边权；
• 重构后得到一棵树或者森林。当且仅当原图不联通，重构得到森林；
• 若原图联通，满足比原图新增了 n-1 个结点，边权的结点编号 x 满足 x\in(n,2n)；
• 最小生成树重构得到大根堆，最大生成树反之^1；
• 重构树中从 x 到 y 的简单路径中经过的非叶子结点为生成图中 x 到 y 路径上经过的边权；

经典例题

• \texttt{P1967 [NOIP 2013 提高组] 货车运输}
• \texttt{P2245 星际导航}

对于求形如求路径最小值最大/最大值最小的问题，首先考虑进行一个最小/大生成树，然后在其中求简单路径的最值。因为不在生成树里面的肯定不优于现在的答案^2，不进行考虑。

因为这两道题基本一样，所以只考虑 \texttt{P1967}。

在求得最大生成树后，我们需要求得生成树简单路径上的最小值。从重构树的性质，我们显然可以得知 x\to y 的简单路径的最大值最小的结点是 \text{lca}(x,y)。

因为 x\to y 的路径上，所有的边边权最小的一个即为答案。而最大生成树的重构树是小根堆，答案即为 val_{\text{lca}(x,y)}。

::::info[code]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 1e4+5;
const int M = 5e4+5;

struct node{
    int x,y,z;
}a[M];

struct edge{
    int ne,to;
}e[M<<2];
int cntE,pre[N<<1];

int n,m;
int f[N<<1];
int val[N<<1];

bool vis[N<<1];
int dep[N<<1];
int wei[N<<1];
int fa[N<<1];
int wson[N<<1];
int cntId,id[N<<1];
int top[N<<1];

inline bool cmp(node x,node y){
    return x.z > y.z;
}

inline void add(int x,int y){
    e[++cntE] = (edge){pre[x],y};
    pre[x] = cntE;
}

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void dfs1(int u,int father){
    dep[u] = dep[father]+1;
    vis[u] = true;
    fa[u] = father;

    wei[u] = 1;
    for(int i = pre[u]; i; i=e[i].ne){
        int v = e[i].to;
        if(v != father){
            dfs1(v,u);
            wei[u] += wei[v];
            if(wei[v] > wei[wson[u]])
                wson[u] = v;
        }
    }
}

inline void dfs2(int u,int t){
    id[u] = ++cntId;
    top[u] = t;

    if(wson[u]) dfs2(wson[u],t);
    for(int i = pre[u]; i; i=e[i].ne){
        int v = e[i].to;
        if(v != fa[u] && v != wson[u])
            dfs2(v,v);
    }
}

inline int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        x = fa[top[x]];
    }

    return (dep[x] < dep[y] ? x : y);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    cin >> n >> m;

    int x,y,z;
    for(int i = 1; i <= m; i++){
        cin >> x >> y >> z;
        a[i] = (node){x,y,z};
    }

    sort(a+1,a+1+m,cmp);

    int cnt = n;
    for(int i = 1; i < (n<<1); i++)
        f[i] = i;

    for(int i = 1; i <= m; i++){
        int x = find(a[i].x);
        int y = find(a[i].y);

        if(x != y){
            cnt++;
            add(x,cnt),add(cnt,x);
            add(y,cnt),add(cnt,y);
            f[x] = f[y] = cnt;
            val[cnt] = a[i].z;
        }
    }

    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        cntId = 0;
        dfs1(find(i),0);
        dfs2(find(i),find(i));
    }

    int T;
    cin >> T;
    while(T--){
        cin >> x >> y;
        if(find(x) != find(y))
            cout << -1 << endl;
        else cout << val[lca(x,y)] << endl;
    }
    return 0;
}

::::

习题讲解

P13548 [OOI 2022] Air Reform

简化题意，给定 n 个点 m 条无向边图 G，设 v(G,u,v) 表示图 G 中边 x\to y 的权值，路径代价表示路径 a_1\to a_2\to\dots\to a_k 上最大的权值 \max\limits_{i\in[1,k)}v(G,a_i,a_{i+1})，路径权值 val(G,x,y) 为 x 到 y 的所有路径中最小的路径代价。

钦定 G' 为 G 的补图（即边集为 G 边集对于完全图边集的补集），其边权 v(G',x,y)=val(G,x,y)，求 val(G',x,y)。

先考虑暴力，这样询问很难不让人想到 kruskal 重构树。对 G 跑一遍重构树，然后重构树维护暴力建补图，再跑一遍重构树即可获得 O(n+n^2\log n+m\log n) 的高昂时间复杂度解法。

::::info[\texttt{code}]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 2e5+5;

struct node{
    int idx,x,y,z;

    bool operator <(node x) const {
        return this->z < x.z;
    }
}a[N],b[N<<1];

int n,m,f[N<<1];
vector<int > e[N<<1];
map<pair<int,int >,bool > table;
int cntNode,kurskalVal[N<<1];

int fa[N<<1],dep[N<<1];
int sz[N<<1],wson[N<<1];
int cntId,id[N<<1];
int top[N<<1];

inline void init(int n);

inline bool cmp(node x,node y){
    return x.idx < y.idx;
}

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void merge(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy) f[fx] = fy;
}

inline void dfs1(int x,int father){
    fa[x] = father;
    dep[x] = dep[father] + 1;

    sz[x] = 1;
    for(auto y : e[x]){
        if(y != father){
            dfs1(y,x);
            sz[x] += sz[y];
            if(sz[y] > sz[wson[x]])
                wson[x] = y;
        }
    }
}

inline void dfs2(int x,int TOP){
    id[x] = ++cntId;
    top[x] = TOP;

    if(wson[x]) dfs2(wson[x],TOP);
    for(auto y : e[x]){
        if(y != fa[x] && y != wson[x])
            dfs2(y,y);
    }
}

inline int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    int T,G;
    cin >> T >> G;
    while(T--){
        cin >> n >> m;

        init(n);

        int x,y,z;
        for(int i = 1; i <= m; i++){
            cin >> x >> y >> z;
            a[i] = (node){i,x,y,z};
            table[make_pair(x,y)] = true;
            table[make_pair(y,x)] = true;
        }

        sort(a+1,a+1+m);

        for(int i = 1; i <= m; i++){
            x = a[i].x,y = a[i].y,z = a[i].z;
            int fx = find(x),fy = find(y);

            if(fx != fy){
                kurskalVal[++cntNode] = z;
                merge(fx,cntNode),merge(fy,cntNode);
                e[fx].push_back(cntNode),e[cntNode].push_back(fx);
                e[fy].push_back(cntNode),e[cntNode].push_back(fy);
            }
        }

        dfs1(cntNode,0);
        dfs2(cntNode,cntNode);

        int cntB = 0;
        for(int i = 1; i < n; i++)
            for(int j = i+1; j <= n; j++)
                if(table.find(make_pair(i,j)) == table.end())
                    b[++cntB] = (node){0,i,j,kurskalVal[lca(i,j)]};

        sort(b+1,b+cntB+1);

        memset(wson,0,sizeof(wson));
        cntNode = n,cntId = 0;
        for(int i = 1; i <= (n<<1); i++){
            f[i] = i;
            e[i].clear();
            kurskalVal[i] = -1;
        }

        for(int i = 1; i <= cntB; i++){
            x = b[i].x,y = b[i].y,z = b[i].z;
            int fx = find(x),fy = find(y);

            if(fx != fy){
                kurskalVal[++cntNode] = z;
                merge(fx,cntNode),merge(fy,cntNode);
                e[fx].push_back(cntNode),e[cntNode].push_back(fx);
                e[fy].push_back(cntNode),e[cntNode].push_back(fy);
            }
        }

        dfs1(cntNode,0);
        dfs2(cntNode,cntNode);

        sort(a+1,a+1+m,cmp);

        for(int i = 1; i <= m; i++)
            cout << kurskalVal[lca(a[i].x,a[i].y)] << " ";
        cout << endl;
    }
    return 0;
}

inline void init(int n){
    for(int i = 1; i <= (n<<1); i++){
        f[i] = i;
        e[i].clear();
        kurskalVal[i] = -1;
    }

    table.clear();

    cntId = 0;
    cntNode = n;
    memset(wson,0,sizeof(wson));
}

::::

::::warning[正解优化（对训练 kruskal 重构树没有意义）]

发现难点在于暴力建补图，量级是极大的。那不妨考虑直接求解最小生成树，然后根据其构建 kruskal 重构树。

使用 Boruvka 算法进行构建最小生成树，遍历 n 个点至多 \log n 轮，发现每个点的连边最高可达 n-1 条，考虑如何优化。

算法进行时考虑一个联通块如何连边。显然的是，需要保证连接对象不处于同一个联通块，且在原图中没有连边。

不妨令每一个点都要连出去恰好一条边，每轮一个联通块至多连出去或者被连一条边，每轮结束后把连边的联通块合并。

思考如何连，显然可以从点 x 往上倍增到第一个不包含 x 的祖先，连边即可。

一种可行的方法就是在 dfs 序上往前或往后找，找到第一个不在 x 同一个联通块的结点，取两者 lca 更小者即可。

不妨先记录一下，记录 n 叶子结点的 dfs 序和颜色，再 O(n\log n) 按 dfs 序升序排序，然后 O(n) 预处理一下前后缀的最值和次值。

对于前缀坐标最大值、前缀坐标次大值，强制钦定这两者的颜色是不同的，后缀最小和次小是同样的。然后对于一个点 x，可以直接 O(1) 跳到一个满足的前后缀，因为两者必有一个不是同一个颜色的。

第二个显然是好考虑的，因为在跳的过程中触发原图有边的失配是 O(m) 级的，可以接受。

那么一轮的时间复杂 O(n+m)。

在每一轮选出边的时候，同步构建一个新的 kruskal 重构树。最后 m 次 O(\log n) 询问即可。

总时间复杂度为 O(n+m\log n+n\log^2 n+(n+m)\log^2 n)。

:::info[\texttt{code}]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 2e5+5;

struct node{
    int idx,x,y,z;

    bool operator <(const node x) const {
        return this->z < x.z;
    }
}a[N];

struct point{
    int idx,dfs,col;
    bool operator <(const point x) const {
        return this->dfs < x.dfs;
    }
};

int n,m,f[N<<1];
int cntBlock;
vector<int > e[N<<1];
int cntNode,kurskalVal[N<<1];
int newKurskalVal[N<<1];
vector<node > edgeVec;
vector<node > NewEdgeVec;
vector<node > edgeAns;

int fa[N<<1],dep[N<<1];
int sz[N<<1],wson[N<<1];
int cntId,id[N<<1];
int g[N<<1],top[N<<1];

vector<point > arr;
int preMax[N],preSecMax[N];
int sufMin[N],sufSecMin[N];
bitset<1> tickNode[N<<1];

unordered_map<lint,bool > hashTable;

inline void init(int n);

inline lint checkHash(int x,int y){
    return 1ll * x * 1000000 + y;
}

inline bool cmp(node x,node y){
    return x.idx < y.idx;
}

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void merge(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy) f[fx] = fy;
}

inline void dfs1(int x,int father){
    fa[x] = father;
    dep[x] = dep[father] + 1;

    sz[x] = 1;
    for(auto y : e[x]){
        if(y != father){
            dfs1(y,x);
            sz[x] += sz[y];
            if(sz[y] > sz[wson[x]])
                wson[x] = y;
        }
    }
}

inline void dfs2(int x,int TOP){
    id[x] = ++cntId;
    g[cntId] = x;
    top[x] = TOP;

    if(wson[x]) dfs2(wson[x],TOP);
    for(auto y : e[x]){
        if(y != fa[x] && y != wson[x])
            dfs2(y,y);
    }
}

inline int lca(int x,int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    int T,G;
    cin >> T >> G;
    while(T--){
        cin >> n >> m;

        init(n);

        int x,y,z;
        for(int i = 1; i <= m; i++){
            cin >> x >> y >> z;
            a[i] = (node){i,x,y,z};
            hashTable[checkHash(x,y)] = true;
            hashTable[checkHash(y,x)] = true;
        }

        sort(a+1,a+1+m);

        for(int i = 1; i <= m; i++){
            x = a[i].x,y = a[i].y,z = a[i].z;
            int fx = find(x),fy = find(y);

            if(fx != fy){
                kurskalVal[++cntNode] = z;
                merge(fx,cntNode),merge(fy,cntNode);
                e[fx].push_back(cntNode),e[cntNode].push_back(fx);
                e[fy].push_back(cntNode),e[cntNode].push_back(fy);
            }
        }

        dfs1(cntNode,0);
        dfs2(cntNode,cntNode);

        cntId = 0,cntNode = n;
        for(int i = 1; i <= (n<<1); i++){
            f[i] = i,wson[i] = 0;
            e[i].clear();
            newKurskalVal[i] = -1;
        }

        edgeAns.clear();
        while(cntBlock > 1){
            arr.clear(),edgeVec.clear();
            NewEdgeVec.clear();

            for(int i = 1; i <= n; i++){
                preMax[i] = preSecMax[i] = 0;
                sufMin[i] = sufSecMin[i] = 0;
                f[i] = find(i);
                tickNode[i].reset();
                arr.push_back((point){i,id[i],f[i]});
            }

            sort(arr.begin(),arr.end());
            for(int i = 1; i <= n; i++){
                int idx = i - 1;
                preMax[i] = i;
                if(i == 1){
                    preSecMax[i] = 0;
                    continue;
                }
                if(arr[idx].col != arr[preMax[i-1]-1].col)
                    preSecMax[i] = preMax[i-1];
                else preSecMax[i] = preSecMax[i-1];
            }

            for(int i = n; i >= 1; i--){
                int idx = i - 1;
                sufMin[i] = i;
                if(i == n){
                    sufSecMin[i] = n+1;
                    continue;
                }
                if(arr[idx].col != arr[sufMin[i+1]-1].col)
                    sufSecMin[i] = sufMin[i+1];
                else sufSecMin[i] = sufSecMin[i+1];
            }

            for(int i = 1; i <= n; i++){
                int idx = i-1,l = i-1,r = i+1;

                while(l >= 1){
                    if(arr[idx].col == arr[l-1].col){
                        l = preSecMax[l];
                        continue;
                    }
                    if(hashTable.find(checkHash(arr[idx].idx,arr[l-1].idx)) != hashTable.end())
                        l--;
                    else break;
                }

                while(r <= n){
                    if(arr[idx].col == arr[r-1].col){
                        r = sufSecMin[r];
                        continue;
                    }
                    if(hashTable.find(checkHash(arr[idx].idx,arr[r-1].idx)) != hashTable.end())
                        r++;
                    else break;
                }

                int lca1 = -1,lca2 = -1,lIdx = -1,rIdx = -1,Idx = arr[idx].idx;
                if(1 <= l && l <= n) lIdx = arr[l-1].idx,lca1 = lca(lIdx,Idx);
                else l = -1;
                if(1 <= r && r <= n) rIdx = arr[r-1].idx,lca2 = lca(rIdx,Idx);
                else r = -1;
                if(l == -1 && r == -1) continue;
                if(l != -1 && r != -1){
                    if(kurskalVal[lca1] < kurskalVal[lca2])
                        edgeVec.push_back((node){f[i],Idx,lIdx,kurskalVal[lca1]});
                    else edgeVec.push_back((node){f[i],Idx,rIdx,kurskalVal[lca2]});
                }else if(l != -1) edgeVec.push_back((node){f[i],Idx,lIdx,kurskalVal[lca1]});
                else if(r != -1) edgeVec.push_back((node){f[i],Idx,rIdx,kurskalVal[lca2]});
            }

            sort(edgeVec.begin(),edgeVec.end());
            for(auto val : edgeVec){
                x = val.x,y = val.y,z = val.z;
                int fx = find(x),fy = find(y);
                if(fx != fy && tickNode[fx] == false){
                    cntBlock--,merge(fx,fy);
                    edgeAns.push_back(val);
                }
                tickNode[fx].set();
            }
        }

        for(int i = 1; i <= (n<<1); i++)
            f[i] = i;

        sort(edgeAns.begin(),edgeAns.end());

        for(auto val : edgeAns){
            x = val.x,y = val.y,z = val.z;
            int fx = find(x),fy = find(y);
            newKurskalVal[++cntNode] = z;
            merge(fx,cntNode),merge(fy,cntNode);
            e[fx].push_back(cntNode),e[cntNode].push_back(fx);
            e[fy].push_back(cntNode),e[cntNode].push_back(fy);
        }

        dfs1(cntNode,0);
        dfs2(cntNode,cntNode);

        sort(a+1,a+1+m,cmp);

        for(int i = 1; i <= m; i++)
            cout << newKurskalVal[lca(a[i].x,a[i].y)] << " ";
        cout << endl;
    }
    return 0;
}

inline void init(int n){
    for(int i = 1; i <= (n<<1); i++){
        f[i] = i;
        wson[i] = 0;
        e[i].clear();
        kurskalVal[i] = -1;
    }

    hashTable.clear();
    cntId = 0;
    cntBlock = cntNode = n;
}

:::

::::

P4768 [NOI2018] 归程

简化题意，给出一个 n 个结点 m 条边的无向连通图，每条边有两个边权 l_i,h_i。每次询问给出一个二元组 (s,d)，边权 h_i\le d 的边我们称为“不好的边”。

你需要从 s 号点出发回到 1 号点。每次询问时，你的状态是“好的”。当你经过任意一条“不好的边”，你的状态会在经过这条边的一开始变成“不好的”。你需要选出一条路径使得在“不好的”状态下经过的边的边权 l_i 的和尽可能小。

一开始的思路是 v\to1 中满足 \min(l_{v},\dots,l_{1}) 最大的这条路径，走到第一个不好的边求最短路，但是这个贪心显然是可以轻松卡掉的。

这个时候不妨考虑所有通过”好的“边连接的联通块中，v 能抵达的点。对边权 h_i 跑一遍 kruskal 重构树，根据重构树的性质，从重构树上 v 的父亲往上爬到第一个点权 h_i\le d 的点结束。路径上除去起点终点的所有点的另一个儿子即这个联通块内的结点。

当然，还应该算上 v 父亲（如果这条边是“好的”）子树内所有叶子结点（因为权值 d 显然比这个父亲更大也更优）。

考虑联通块内从任意一点假设地开始通过一个“不好的”边前往 1 号结点。求这所有的点的最短路。

贪心一下很对，因为如果最短路上，下一条边不是“不好的”边，那么一定是抵达联通块内其他点，取 \min 时会被忽略掉。

给图内每个点挂个点权 val_i 表示 i\to 1 的最短路。然后重构树上把两个儿子的权值取 \min 挂到父亲的 val 上。每次倍增到一个符合条件的路径终点的儿子（x=0 即根的父亲强制结束），这个点的 val 值即为通解。

排序是 O(m\log m)，倍增预处理祖先结点和跑一遍 dijkstra 都是 O(n\log n)，构建重构树、跑一遍树剖和挂点都是 O(n)，一次询问倍增跳点 O(\log n)，总时间复杂度 O(n+n\log n+q\log n)。

这种在限制了路径上最值边界的 trick 叫最小/大瓶颈路。

::::info[code]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 2e5+5;
const int M = 4e5+5;
const int INF = 2e9;

struct node{
    int u,v,l,h;
}a[M];

struct edge{
    int ne,to,l;
}g[M<<1];
int cntE,pre[N];

struct queueNode{
    int x,dis;

    bool operator <(queueNode x) const {
        return this->dis < x.dis;
    }
    bool operator >(queueNode x) const {
        return this->dis > x.dis;
    }
};
int dis[N];
bitset<1> vis[N];
priority_queue<queueNode,vector<queueNode>,greater<queueNode> > que;

int n,m,f[N<<1];
vector<int > e[N<<1];
int st[N<<2][24];

int cntId,id[N<<1];
int fa[N<<1],dep[N<<1];
int sz[N<<1],wson[N<<1];
int top[N<<1];

int treeH[N<<1];
int treeVal[N<<1];

inline bool cmp(node x,node y){
    return x.h > y.h;
}

inline void add(int x,int y,int z){
    g[++cntE] = (edge){pre[x],y,z};
    pre[x] = cntE;
}

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void merge(int x,int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy) f[fx] = fy;
}

inline void dijkstra(int s){
    dis[s] = 0;
    que.push((queueNode){s,0});
    while(!que.empty()){
        queueNode u = que.top();
        que.pop();
        if(vis[u.x] == true) continue;
        vis[u.x].set();
        for(int i = pre[u.x]; i; i=g[i].ne){
            int v = g[i].to,len = g[i].l;
            if(u.dis + len < dis[v]){
                dis[v] = u.dis + len;
                que.push((queueNode){v,dis[v]});
            }
        }
    }
}

inline void dfs1(int x,int father){
    fa[x] = father;
    dep[x] = dep[father] + 1;

    sz[x] = 1;
    for(int y : e[x]){
        if(y != father){
            dfs1(y,x);
            sz[x] += sz[y];
            if(sz[y] > sz[wson[x]])
                wson[x] = y;
        }
    }
}

inline void dfs2(int x,int TOP){
    id[x] = ++cntId;
    top[x] = TOP;

    if(wson[x]){
        dfs2(wson[x],TOP);
        treeVal[x] = treeVal[wson[x]];
    }else treeVal[x] = dis[x];
    for(int y : e[x]){
        if(y != fa[x] && y != wson[x]){
            dfs2(y,y);
            treeVal[x] = min(treeVal[x],treeVal[y]);
        }
    }
}

inline int solve(int v,int d){
    int p = 0;
    while(st[v][p] != 0 && treeH[st[v][p]] >= d)
        p++;
    p--;
    while(p >= 0){
        if(treeH[st[v][p]] > d)
            v = st[v][p];
        p--;
    }
    return treeVal[v];
}

inline void init();

inline void initSt(int n){
    for(int i = 1; i <= n; i++)
        st[i][0] = fa[i];

    for(int j = 1; j <= 20; j++)
        for(int i = 1; i <= n; i++)
            st[i][j] = st[st[i][j-1]][j-1];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    int T;
    cin >> T;
    while(T--){
        cin >> n >> m;

        init();

        for(int i = 1; i <= m; i++){
            int u,v,l,h;
            cin >> u >> v >> l >> h;
            a[i] = (node){u,v,l,h};
            add(u,v,l),add(v,u,l);
        }

        dijkstra(1);
        sort(a+1,a+1+m,cmp);

        int cntNode = n;
        for(int i = 1; i <= m; i++){
            int x = a[i].u,y = a[i].v,z = a[i].h;
            int fx = find(x),fy = find(y);
            if(fx != fy){
                treeH[++cntNode] = z;
                merge(x,cntNode),merge(y,cntNode);
                e[fx].push_back(cntNode),e[cntNode].push_back(fx);
                e[fy].push_back(cntNode),e[cntNode].push_back(fy);
            }
        }

        dfs1(cntNode,0);
        dfs2(cntNode,cntNode);
        initSt(cntNode);

        int Q,K,S,v0,d0;
        int lastans = 0;
        cin >> Q >> K >> S;
        while(Q--){
            cin >> v0 >> d0;
            int v = (v0 + K * lastans - 1) % n + 1;
            int d = (d0 + K * lastans) % (S + 1);
            lastans = solve(v,d);
            cout << lastans << endl;
        }
    }
    return 0;
}

inline void init(){
    for(int i = 1; i <= (n<<1); i++){
        f[i] = i;
        e[i].clear();
    }

    cntE = cntId = 0;
    memset(pre,0,sizeof(pre));
    memset(wson,0,sizeof(wson));
    memset(st,0,sizeof(st));

    for(int i = 1; i <= n; i++){
        vis[i].reset();
        treeVal[i] = dis[i] = INF;
    }
}

::::

P9638 「yyOI R1」youyou 的军训

一些 tips 放在了这里 https://www.luogu.com.cn/article/0as8n2fv。

考虑是否适用于 kruskal 重构树，不难发现修改的限制条件“不改变相对顺序”就是防止重构树的形状发生改变设计的，只用单纯修改重构树上点权即可。

简单来说，这题就是瓶颈路问题的板子。

首先考虑跑一遍最大生成树。因为对于一个连接两个联通块的边 x\leftrightarrow y，若其权值 z 小于另一条同样连接这个联通块的 x'\leftrightarrow y' 的权值 z'，当 x'\leftrightarrow y' 因为小于敏感度断掉时，x\leftrightarrow y 一定也断掉。因为没有边长这一说，所以这样选一定是不劣的。

进行操作一时，不妨先用一个变量 limit 记录。初始设置为 -\infty，这样不会有边断掉。

此时考虑在 limit 的限制条件下进行操作 2。本质上就是寻找最大瓶颈，即找到 x 的最浅祖先结点满足该结点的权值 \ge limit。此时该子树内所有结点都在一个联通块里，叶子结点数量即为答案。

对于操作三，我们找到对应原边后修改这两个点的 \text{lca} 的权值即可。但是需要注意的是，因为这条边就算变大如果已经断掉了也不会恢复，那么我们需要把这个修改（如果有效）先存起来，进行新的操作一后更新。

排序建 kruskal 重构树是 O(m\log m+m)，修改找原边用映射 O(n)，求 \text{lca} 用树剖 O(\log n)，倍增找瓶颈 O(\log n)，跑 dfs 挂权值和树剖均是 O(n)。最劣的时间复杂度为 O(m\log m+m+n+q\log n)。

::::info[\texttt{code}]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define ldouble long double
#define endl '\n'
using namespace std;
const int N = 4e5+5;

struct edge{
    int idx,x,y,z;
    bitset<1> is;

    edge(int a = 0,int b = 0,int c = 0,int d = 0):
        idx(a),x(b),y(c),z(d) {}

    bool operator <(const edge &other) const {
        return this->z < other.z;
    }
    bool operator >(const edge &other) const {
        return this->z > other.z;
    }
}e[N];
int table[N];

struct node{
    int x,y,z;
}history[N];
int cnt;

int n,m,q;
int f[N<<1];
int limit;

vector<int > g[N<<1];
int cntId,id[N<<1];
int fa[N<<1][30],dep[N<<1];
int sz[N<<1],wson[N<<1];
int top[N<<1],val[N<<1];
int cntLeaves[N<<1];

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void dfs1(int x,int father){
    fa[x][0] = father,sz[x] = 1;
    dep[x] = dep[father] + 1;
    for(int y : g[x]){
        if(y == father)
            continue;
        dfs1(y,x);
        sz[x] += sz[y];
        if(sz[y] > sz[wson[x]])
            wson[x] = y;
    }
}

inline void dfs2(int x,int TOP){
    id[x] = ++cntId;
    top[x] = TOP;
    if(wson[x]){
        dfs2(wson[x],TOP);
        cntLeaves[x] += cntLeaves[wson[x]];
    }else cntLeaves[x] = 1;
    for(int y : g[x]){
        if(y != fa[x][0] && y != wson[x]){
            dfs2(y,y);
            cntLeaves[x] += cntLeaves[y];
        }
    }
}

inline int lca(int x,int y){
    if(find(x) != find(y))
        return 0;

    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        x = fa[top[x]][0];
    }
    return dep[x] < dep[y] ? x : y;
}

inline int query(int x){
    int idx = 0;
    while(fa[x][idx] && val[fa[x][idx]] >= limit)
        idx++;

    if(idx == 0) return 1;

    idx--;
    while(idx >= 0){
        if(val[fa[x][idx]] >= limit)
            x = fa[x][idx];
        idx--;
    }

    return cntLeaves[x];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    cin >> n >> m >> q;

    int x,y,k;
    for(int i = 1; i <= m; i++){
        cin >> x >> y >> k;
        e[i] = edge(i,x,y,k);
        e[i].is.reset();
    }

    sort(e+1,e+1+m,greater<edge>());

    for(int i = 1; i <= (n<<1); i++)
        f[i] = i;

    for(int i = 1; i <= m; i++)
        table[e[i].idx] = i;

    int cntNode = n;
    for(int i = 1; i <= m; i++){
        int x = e[i].x,y = e[i].y;
        int fx = find(x),fy = find(y);
        if(fx != fy){
            e[i].is.set();
            val[++cntNode] = e[i].z;
            f[fx] = cntNode,f[fy] = cntNode;
            g[fx].push_back(cntNode),g[cntNode].push_back(fx);
            g[fy].push_back(cntNode),g[cntNode].push_back(fy);
        }
        if(cntNode == (n<<1)-1)
            break;
    }

    val[0] = -1;
    for(int idx = cntNode; idx >= 1; idx--){
        if(!id[idx]){
            dfs1(idx,0);
            dfs2(idx,idx);
        }
    }

    for(int j = 1; (1<<j) <= (n<<1); j++)
        for(int i = 1; i <= (n<<1); i++)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    int op;
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> x;
            limit = x;

            for(int i = 1; i <= cnt; i++)
                val[lca(history[i].x,history[i].y)] = history[i].z;
            cnt = 0;
        }else if(op == 2){
            cin >> x;
            cout << query(x) << endl;
        }else if(op == 3){
            cin >> x >> y;
            edge p = e[table[x]];
            if(p.is == true)
                history[++cnt] = (node){p.x,p.y,y};
        }
    }
    return 0;
}

::::

P3684 [CERC2016] 机棚障碍 Hangar Hurdles

题意就是给一个 01 矩阵，可以从每个点展开一个长度为奇数的正方形。要求询问两个点之间，可以通过的最大正方形。

我们给每一个点预处理赋予权值 v_{x,y}，代表位于 (x,y) 最大可展开的正方形的长度。

发现时间复杂度最多是平方带一个 \log 的，不妨思考枚举每个坐标然后二分一下。

此时二分的检验应该是 O(1) 的。

预处理是好文明。我们再 O(n^2) 预处理出 d_{x,y} 表示从 (x,y) 往下最长空白长度。再 O(n^2) 预处理出 f_{x,y} 表示以 (x,y) 为左上角向右下可以延伸的最大正方形。

第一个显然是好做的。第二个显然也是好做的。

我们不妨模拟一下，推导 (x,y) 时，我们往后寻找到 (x+k,y) 时，需要满足 \min\limits_{i\in[x,x+k]} d_{i,y}\ge k+1。一个显然的是，f_{x+1,y}\ge f_{x,y}-1，不妨继承了之后再从已经有的右边界向右延伸。

对于求解 \min 的问题，不妨用单调队列维护。

做完后我们就可以 O(n^2\log n) 求 v_{x,y} 了，然后再 O(n^2) 建一下图，相邻点的边权为权值更小值。

然后跑个重构树就做完了。

为了辨别并查集数组把 f 用 g 代替。

::::info[\texttt{code}]

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 1e3+5;

struct node{
    int x,y,z;

    node(int a = 0,int b = 0,int c = 0):
        x(a),y(b),z(c) {}

    inline bool operator <(const node& other) const {
        return this->z < other.z;
    }
    inline bool operator >(const node& other) const {
        return this->z > other.z;
    }
}arr[(N*N)<<1];

int n,m,cntNode;
bool a[N][N];
int f[N*N*2],v[N][N];
int d[N][N],g[N][N];
deque<int > que;
vector<int> e[N*N*2];
int val[N*N*2];

int fa[N*N*2];
int dep[N*N*2];
int lb[N*N*2];

inline int getId(int x,int y){
    return n*(x-1) + y;
}

inline bool check(int x,int y,int k){
    int lx = x-k+1,ly = y-k+1,rx = x+k-1,ry = y+k-1;
    if(!(1 <= lx && lx <= n && 1 <= ly && ly <= n)) return false;
    if(!(1 <= rx && rx <= n && 1 <= ry && ry <= n)) return false;
    return g[lx][ly] >= k*2-1;
}

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void dfs(int x,int father){
    fa[x] = father;
    dep[x] = dep[father] + 1;

    int p = lb[father],q = lb[p];
    lb[x] = (dep[father]-dep[p] == dep[p]-dep[q] ? q : father);

    for(int y : e[x]){
        if(y != father)
            dfs(y,x);
    }
}

inline int lca(int x,int y){
    if(dep[x] < dep[y]) swap(x,y);
    while(dep[x] > dep[y]){
        if(dep[lb[x]] >= dep[y])
            x = lb[x];
        else x = fa[x];
    }
    while(x != y){
        if(lb[x] != lb[y])
            x = lb[x],y = lb[y];
        else x = fa[x],y = fa[y];
    }
    return x;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    // freopen("app.in","r",stdin);
    // freopen("app.out","w",stdout);

    cin >> n;

    char character;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> character;
            a[i][j] = (character == '.');
        }
    }

    for(int i = n; i >= 1; i--){    
        for(int j = 1; j <= n; j++){
            if(!a[i][j]) continue;
            d[i][j] = d[i+1][j] + 1;
        }
    }

    for(int i = 1; i <= n; i++){
        int end = 1;

        que.clear();
        for(int j = 1; j <= n; j++){
            if(!a[i][j]) continue;
            end = max(end,j+1);
            g[i][j] = max(1,g[i][j-1]-1);

            while(!que.empty() && que.front() < j)
                que.pop_front();
            if(que.empty()) que.push_back(j);

            while(a[i][end]){
                while(!que.empty() && d[i][que.back()] >= d[i][end])
                    que.pop_back();
                que.push_back(end);

                if(g[i][j]+1 > d[i][que.front()])
                    break;
                else g[i][j]++;

                end++;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int l = 1,r = n;
            while(l <= r){
                int mid = l + r >> 1;
                if(check(i,j,mid)){
                    v[i][j] = (mid<<1) - 1;
                    l = mid + 1;
                }else r = mid - 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(i > 1) arr[++m] = node(getId(i-1,j),getId(i,j),min(v[i-1][j],v[i][j]));
            if(j > 1) arr[++m] = node(getId(i,j-1),getId(i,j),min(v[i][j-1],v[i][j]));
        }
    }

    for(int i = 1; i <= n*n*2; i++)
        f[i] = i;

    sort(arr+1,arr+1+m,greater<node>());

    cntNode = n*n;
    for(int i = 1; i <= m; i++){
        int x = arr[i].x,y = arr[i].y,z = arr[i].z;
        int fx = find(x),fy = find(y);
        if(fx != fy){
            val[++cntNode] = z,f[fx] = f[fy] = cntNode;;
            e[fx].push_back(cntNode),e[cntNode].push_back(fx);
            e[fy].push_back(cntNode),e[cntNode].push_back(fy);
        }
    }

    dfs(cntNode,0);

    int q;
    cin >> q;
    int Ax,Ay,Bx,By;
    while(q--){
        cin >> Ax >> Ay >> Bx >> By;
        cout << val[lca(getId(Ax,Ay),getId(Bx,By))] << endl;
    }
    return 0;
}

::::

P4197 [ONTAK2010] Peaks

很典的两个 trick 结合。

第一个 trick 是归程中倍增求祖先，第二个是查询子树内第 k 值。

简单来说，先倍增求 x 限制下的最高祖先结点，把非叶子设置成无穷小，然后求第 k 大即可。