「NOI 2018」归程「Kruskal 重构树」

题解

Kruskal重构树：每次一条边连接两个集合，建一个新点，点权为该边边权；把这两个集合的根连向新点。

性质：（如果求的是最大生成树）叶子结点是图中实际结点；叶子到根路径上点权递减；两点间lca的权值就是这两点走最大生成树经过的最小边

然后对于这题我们建重构树然后每次倍增找到一个深度极小的祖先u，返回u子树内实结点dis的最小值即可

#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 4e5 + 10;
const ll INF = 1e15;
int n, m, q, k, s;
struct Edge {
    int v, w, nxt;
} e[N * 2];
int hd[N], c;
ll d[N];
void add(int u, int v, int w) {
    e[c] = (Edge) {v, w, hd[u]}; hd[u] = c ++;
}
struct Node {
    int u; ll d;
    bool operator < (const Node &b) const { return d > b.d; }
};
void dijkstra() {
    fill(d + 1, d + n + 1, INF); d[1] = 0;
    priority_queue<Node> pq; pq.push((Node) {1, d[1]});
    while(pq.size()) {
        Node k = pq.top(); pq.pop();
        if(d[k.u] < k.d) continue ;
        for(int i = hd[k.u]; ~ i; i = e[i].nxt) {
            if(d[e[i].v] > d[k.u] + e[i].w) {
                pq.push((Node) {e[i].v, d[e[i].v] = d[k.u] + e[i].w});
            }
        }
    }
}
struct Edge2 {
    int u, v, w;
    bool operator < (const Edge2 &e) const { return w > e.w; }
} e2[N];
int f[N], T[N], p[N][22], w[N], nn;
ll dt[N];
int find(int u) { return u == f[u] ? u : f[u] = find(f[u]); }
void kruskal() {
    sort(e2 + 1, e2 + m + 1);
    for(int i = 1; i <= n; i ++) f[i] = T[i] = i, dt[i] = d[i];
    int cnt = 0; nn = n;
    for(int i = 1; i <= m; i ++) {
        int u = find(e2[i].u), v = find(e2[i].v);
        if(u != v) {
            p[T[u]][0] = p[T[v]][0] = ++ nn;
            w[nn] = e2[i].w; p[nn][0] = 0;
            dt[nn] = min(dt[T[u]], dt[T[v]]);
            f[u] = v; T[v] = nn;
            if(++ cnt == n - 1) break ;
        }
    }
    for(int j = 1; j <= 20; j ++)
        for(int i = 1; i <= nn; i ++)
            p[i][j] = p[p[i][j - 1]][j - 1];
}

ll qry(int u, int low) {
    int v = u;
    for(int i = 20; i >= 0; i --) {
        if(p[v][i] && w[p[v][i]] > low) {
            v = p[v][i];
        }
    }
    return dt[v];
}

void solve() {
    scanf("%d%d", &n, &m);
    fill(hd + 1, hd + n + 1, -1); c = 0;
    for(int i = 1; i <= m; i ++) {
        int u, v, l, h;
        scanf("%d%d%d%d", &u, &v, &l, &h);
        add(u, v, l); add(v, u, l);
        e2[i] = (Edge2) {u, v, h};
    }
    dijkstra();
    kruskal();
    scanf("%d%d%d", &q, &k, &s);
    ll lans = 0;
    for(int i = 1; i <= q; i ++) {
        int v, w; scanf("%d%d", &v, &w);
        v = (v + k * lans - 1) % n + 1;
        w = (w + k * lans) % (s + 1);
        printf("%lld\n", lans = qry(v, w));
    }
}

int main() {
    freopen("return.in", "r", stdin);
    freopen("return.out", "w", stdout);
    int T; scanf("%d", &T);
    while(T --) solve();
    fclose(stdin); fclose(stdout);
    return 0;
}