就此也把 Kruskal 重构树的性质总结一下...

Problem

https://www.luogu.org/problemnew/show/P4768

Solution

Kruskal 重构树可以用于求解两点之间任意路径最大边的最小值。

如果是离线的话，可以 Kruskal 做就行了。也是一个贪心的思想。

我们按照 kruskal 求最小⽣成树的方式加边，但每次在加边时，新建⼀个节点，然后把两个联通块（其实是两棵⼆叉树）的根节点作为其左右儿⼦，把边权赋值给新建节点。那么我们可以发现这棵树有几个性质。

1. 是⼀棵⼆叉树；
2. 满⾜父节点的值⼤于等于儿⼦节点，是⼀个大顶堆，这是最关键的⼀点；
3. 原图上任意两点间路径最长边的最小值等于其 lca 的值；

当然如果是从大到小建的话，原理也一样。本题需要倒着建，然后 lca 的意义就变成了路上最短边的最大值。也就是说 u,v 的这个值如果 >T，则 u,v 联通。

则对于点权 >T 的子树，其中的叶子节点属于一个连通块（因为任意叶子节点的任意路径的最短边的最大值 >T），而子树肯定不能与子树外的结点构成连通块（<=T）。

所以只需预处理出每个点到 1 的最短路值，再建 Kruskal 重构树预处理子树 min 值，查询时倍增即可。

Code

程序好像已经经过了 luogu 数据检验可以放心（雾）

luogu 加题速度很快啊， 给管理员点赞

// Code by ajcxsu
// Problem: return

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef long long ll;

template<typename T> void gn(T &x) {
    char ch=getchar();
    x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}

const int N=4e5+10, M=1e6+10;
int h[N], to[M], nexp[M], p=1;
ll W[M], f[N], nw[N];
inline void ins(int a, int b, ll w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
struct Edge { int u, v; ll w; } e[M];
bool cmp(const Edge &a, const Edge &b) { return a.w>b.w; }
int n, m;
ll U;

ll dist[N];
bool S[N];
typedef pair<ll, int> mpair;
void SPFA() {
    CLR(dist, 0x3f), CLR(S, 0);
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    pq.push(mpair(0, 1));
    dist[1]=0;
    int na;
    for(int i=1;i<=n;i++) {
        while(S[pq.top().second] || pq.top().first>dist[pq.top().second]) pq.pop();
        na=pq.top().second, S[na]=1;
        for(int u=h[na];u;u=nexp[u])
            if(dist[to[u]]>dist[na]+W[u] && !S[to[u]])
                dist[to[u]]=dist[na]+W[u], pq.push(mpair(dist[to[u]], to[u]));
    }
}

int fa[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }

const int OP=22;
int gup[N][OP];
void dfs(int x) {
    for(int u=h[x];u;u=nexp[u])
        dfs(to[u]), f[x]=min(f[x], f[to[u]]), gup[to[u]][0]=x;
    if(x<=n) f[x]=dist[x];
}

int main() {
    int T;
    gn(T);
    while(T--) {
        CLR(h, 0), p=1;
        gn(n), gn(m);
        int u, v, w, a;
        for(int i=1;i<=m;i++)
            gn(u), gn(v), gn(w), gn(a),
            ins(u, v, w), ins(v, u, w),
            e[i]={u, v, a};
        sort(e+1, e+1+m, cmp);
        SPFA();
        int idx=n;
        CLR(h, 0), CLR(fa, 0), p=1;
        for(int i=1;i<=n;i++) W[i]=0;
        for(int i=1;i<=m;i++) {
            int af=Find(e[i].u), bf=Find(e[i].v);
            if(af==bf) continue;
            fa[af]=fa[bf]=++idx;
            ins(idx, af, 0), ins(idx, bf, 0);
            nw[idx]=e[i].w;
        }
        CLR(gup, 0), CLR(f, 0x3f);
        dfs(idx);
        for(int j=1;j<OP;j++)
            for(int i=1;i<=idx;i++)
                gup[i][j]=gup[gup[i][j-1]][j-1];
        ll Q,K,S;
        gn(Q), gn(K), gn(S);
        ll lastans=0;
        while(Q--) {
            gn(u), gn(U);
            u=(u+K*lastans-1)%n+1;
            U=(U+K*lastans)%(S+1);
            for(int j=OP-1;j>=0;j--)
                if(nw[gup[u][j]]>U) u=gup[u][j];
            printf("%lld\n", lastans=f[u]);
        }
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-4768.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆