[NOI2018]归程 kruskal重构树

[NOI2018]归程

LG传送门

kruskal重构树模板题。

另一篇文章里有关于kruskal重构树更详细的介绍和更板子的题目。

题意懒得说了，这题的关键在于快速找出从查询的点出发能到达的点（即经过海拔高于水位线的边能到达的点）中距离\(1\)号点最近的距离。

看上去可以kruskal，假设我们把边实现按海拔从大到小排序，考虑我们的重构树的性质：一个小根堆，任意一个点到根节点的路径上的点权单调不升，且这条路径上最浅的高于水位线的点\(u\)的子树中的所有叶节点就是这个点所能到达的所有点。dijkstra预处理每个点到\(1\)的最短路，再在重构树上一遍dfs处理出每棵子树中到\(1\)的最短距离，查询时\(u\)直接倍增求，这题就做完了。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#include <queue>

#define R register

#define I inline

#define B 1000000

using namespace std;

const int N = 200003, M = 400003, inf = 2e9;

char buf[B], *p1, *p2;

I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }

I int rd() {

    R int f = 0;

    R char c = gc();

    while (c < 48 || c > 57)

        c = gc();

    while (c > 47 && c < 58)

        f = f * 10 + (c ^ 48), c = gc();

    return f;

}

int s[N], vis[N], dis[N], f[M], o[M], val[M], son[M][2], dep[M], fa[M][20], n, cnt;

struct edge { int u, v, l, a; }e[M];

vector <pair <int, int> > g[N];

priority_queue <pair <int, int> > q;

I int operator < (edge x, edge y) { return x.a > y.a; }

I int min(int x, int y) { return x < y ? x : y; }

I int find(int x) {

    R int r = x, y;

    while (f[r] ^ r)

        r = f[r];

    while (x ^ r)

        y = f[x], f[x] = r, x = y;

    return r;

}

void dfs(int x, int f) {

    dep[x] = dep[f] + 1, fa[x][0] = f;

    for (R int i = 1; i < 20; ++i)

        fa[x][i] = fa[fa[x][i - 1]][i - 1];

    if (x <= n) {

        o[x] = dis[x];

        return ;

    }

    dfs(son[x][0], x), dfs(son[x][1], x), o[x] = min(o[son[x][0]], o[son[x][1]]);

}

I int query(int x, int y) {

    for (R int i = 19; ~i; --i)

        if (dep[x] - (1 << i) > 0 && val[fa[x][i]] > y)

            x = fa[x][i];

    return o[x];

}

int main() {

    R int T = rd(), m, Q, K, S, i, x, y, z, last;

    while (T--) {

        memset(vis, 0, sizeof vis), n = rd(), m = rd(), last = 0;

        for (i = 1; i <= n; ++i)

            g[i].clear();

        for (i = 1; i <= m; ++i) {

            x =rd(), y = rd(), z =rd(), e[i] = (edge){x, y, z, rd()};

            g[x].push_back(make_pair(y, z)), g[y].push_back(make_pair(x, z));

        }

        for (i = 1; i <= n; ++i)

            s[i] = g[i].size(), dis[i] = inf;

        for (i = 1; i < n << 1; ++i)

            f[i] = i;

        dis[1] = 0, q.push(make_pair(0, 1));

        while (!q.empty()) {

            x = q.top().second, q.pop();

            if (vis[x])

                continue;

            vis[x] = 1;

            for (i = 0; i < s[x]; ++i) {

                y = g[x][i].first, z = g[x][i].second;

                if (dis[y] > dis[x] + z)

                    dis[y] = dis[x] + z, q.push(make_pair(-dis[y], y));

            }

        }

        sort(e + 1, e + m + 1), cnt = n;

        for (i = 1; i <= m; ++i) {

            x = find(e[i].u), y = find(e[i].v);

            if (x ^ y) {

                ++cnt, f[x] = f[y] = cnt, val[cnt] = e[i].a;

                son[cnt][0] = x, son[cnt][1] = y;

            }

        }

        dfs(cnt, 0), Q = rd(), K = rd(), S = rd();

        for (i = 1; i <= Q; ++i) {

            x = (rd() + K * last - 1) % n + 1, y = (rd() + K * last) % (S + 1);

            printf("%d\n", last = query(x, y));

        }

    }

    return 0;

}