Kruskal 重构树

在 Kruskal 最小/大生成树 — Luogu P1967 货车运输 一文中，介绍了 Kruskal 算法是如何生成最小生成树的

如果将两个联通块联通的不是边而是点呢？

这就是 Kruskal 重构树

具体来说就是，我们原来是通过一条边将两个联通块相连接的，现在我们新建立一个点，将这两个联通块的根节点连接到这个点上，原来的边权就是这个新建节点的点权，这样执行下来，我们会得到一棵新的树，这个树有以下两个特征

• 没有 边权
• 保证是一个堆
  • 大根堆还是小根堆要看 原来 生成的是最小还是最大生成树
  • 因为我们保证边权的单调性，故后期新建节点的点权也是单调的，故新树是一个堆

代码实现

// Kru Tree Start
struct k_edge {
    int now, to, hei;
    bool operator<(k_edge b) { return this->hei > b.hei; }
} k_e[M];

struct _set {
    int fa[N << 1];
    void init(int now) {
        now <<= 1;
        for (int i = 1; i <= now; i++) fa[i] = i;
    }
    int get_fa(int now) {
        if (fa[now] == now)
            return now;
        return fa[now] = get_fa(fa[now]);
    }
    int& operator[](int now) { return fa[now]; }
} set;

void kru_tree() {
    edge_init();
    set.init(n);
    std::sort(k_e + 1, k_e + m + 1);
    for (int i = 1; i <= m; i++) {
        int tmp_now = set.get_fa(k_e[i].now), tmp_to = set.get_fa(k_e[i].to);
        if (tmp_now != tmp_to) {
            n++;
            Min_hei[n] = k_e[i].hei;
            add_edge(n, tmp_now);
            add_edge(n, tmp_to);
            set[tmp_now] = n;
            set[tmp_to] = n;
        }
    }
}
// Kru Tree End

「NOI 2018」 归程

题目链接: https://oj.woshiluo.site/problem/2009

我人生中第一次听说强制在线就是这个东西

先跑重构树

如果节点 $u$ 在重构树中可以开到 $v$ 节点，那么 $v$ 节点及其所有子树都可以开车开到，所以我们的目标是找到 $v$ 节点及 $v$ 节点及其所以子树中的到达 $1$ 节点距离最短的一个

找到 $v$ 节点倍增

后者先 $Dijskra$ 求 $1$ 节点到所有节点的最短路，然后重构树建完之后跑一边 $DFS$ 即可

代码

#include <cstdio>
#include <cstring>

#include <queue>
#include <algorithm>

inline int Min(int a, int b) { return a < b? a: b; }

const int N = 2e5 + 1e4;
const int M = 4e5 + 1e4;
const int INF = 0x3f3f3f3f;

int T, _n, n, m;
int Min_dis[ N << 1 ], Min_hei[ N << 1 ], fa[ N << 1 ][30];

// Edge Start
struct edge {
    int to, next, val;
}e[M << 1];
int ehead[N << 1], ecnt;

inline void add_edge(int now, int to, int val = 0) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}

void edge_init(){
    ecnt = 0;
    memset(ehead, 0, sizeof(ehead));
}
// Edge End

// Kru Tree Start
struct k_edge {
    int now, to, hei;
    bool operator< (k_edge b) { return this -> hei > b.hei; }
}k_e[M];

struct _set {
    int fa[N << 1];
    void init(int now) {
        now <<= 1;
        for(int i = 1; i <= now; i ++)
            fa[i] = i;
    }
    int get_fa(int now) {
        if( fa[now] == now )
            return now;
        return fa[now] = get_fa(fa[now]);
    }
    int& operator[] (int now) { return fa[now]; }
}set;

void kru_tree() {
    edge_init();
    set.init(n);
    _n = n;
    std::sort(k_e + 1, k_e + m + 1);
    for(int i = 1; i <= m; i ++) {
        int tmp_now = set.get_fa( k_e[i].now ), tmp_to = set.get_fa( k_e[i].to );
        if( tmp_now != tmp_to ) {
            n ++;
            Min_hei[n] = k_e[i].hei;
            add_edge(n, tmp_now);
            add_edge(n, tmp_to);
            set[tmp_now] = n;
            set[tmp_to] = n;
        }
    }
}
// Kru Tree End

// Dijkstra Start
struct node {
    int now, dis;
    bool operator< (const node &b)const { return this -> dis > b.dis; }
};
std::priority_queue<node> q;

int dis[N << 1];
bool vis[N << 1];

void get_dis(){
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1] = 0;
    q.push((node){1, 0});
    while( ! q.empty() ) {
        node top = q.top(); q.pop();
        if( vis[ top.now ] )
            continue;
        vis[ top.now ] = true;
        for(int i = ehead[ top.now ]; i; i = e[i].next) {
            if( dis[ top.now ] + e[i].val < dis[ e[i].to ] ){
                dis[ e[i].to ] = dis[ top.now ] + e[i].val;
                if( vis[ e[i].to ] == false )
                    q.push( (node){e[i].to, dis[ e[i].to ]} );
            }
        }
    }
}
// Dijkstra End

void get_st(int now = n, int la = 0) {
    if( now <= _n )
        Min_dis[now] = dis[now], Min_hei[now] = INF;
    else
        Min_dis[now] = INF;
    fa[now][0] = la;
    for(int k = 1; k <= 25; k ++)
        fa[now][k] = fa[ fa[now][ k - 1 ] ][ k - 1 ];

    for(int i = ehead[now]; i; i = e[i].next) {
        if( e[i].to == la )
            continue;
        get_st(e[i].to, now);
        Min_dis[now] = Min(Min_dis[ e[i].to ], Min_dis[now]);
    }
}

int get_ans(int from, int p) {
    for(int k = 25; k >= 0; k --) {
        if(fa[from][k] && Min_hei[ fa[from][k] ] > p)
            from = fa[from][k];
    }
    return Min_dis[from];
}

void work() {
    int q, k, s, v, p, lastans = 0;
    scanf("%d%d%d", &q, &k, &s);
    while( q -- ){
        scanf("%d%d", &v, &p);
        v = ( (v + k * lastans - 1) % _n )+ 1;
        p = (p + k * lastans) % (s + 1);
        lastans = get_ans(v, p);
        printf("%d\n", lastans);
    }
}

void init() {
    // I don't know why this fun here.
    // May it's just an useless decoration.
}

void readin() {
    edge_init();
    scanf("%d%d", &n, &m);
    for(int i = 1, v; i <= m; i++) {
        scanf("%d%d%d%d", &k_e[i].now, &k_e[i].to, &v, &k_e[i].hei);
        add_edge(k_e[i].now, k_e[i].to, v);
        add_edge(k_e[i].to, k_e[i].now, v);
    }
}

int main() {
    freopen("return.in", "r", stdin);
    freopen("return.out", "w", stdout);
    scanf("%d", &T);
    while( T -- ) {
        init();
        readin();
        get_dis();
        kru_tree();

        get_st();
        work();
    }
}