P4768 [NOI2018] 归程

2021-08-02 15:56:27


题目大意

给定一张图,每条边都有一个高度和长度,每组询问 $v, p$ 输出从点 $v$ 出发不经过高度小于等于 $p$ 的边能够到达的所有点到点 $1$ 的最小距离。

题解

经典的 Kruskal 重构树了。先预处理从点 $1$ 到所有点的最短路,然后对于高度跑最大生成树建立 Kruskal 重构树(容易证明,对于任意一个无向联通图,其任意两点间,一定存在一条总权值为边权最大值的最短路径,其中最大边权的边属于该图的最大生成树)。这样建立的 Kruskal 重构树每条最大生成树的边所对应的结点形成的二叉树满足小根堆除形态外的性质(很显然吧?)。

根据这样的 Kruskal 重构树的一个性质:每个点 $v$ 在水位线是 $p$ 的情况下不经过积水路段所能到达的所有点在这个 Kruskal 重构树里属于同一个子树(也挺显然的),且它们的 LCA 对应的边的高度一定是小于 $p$ 的情况下极大的。

而由于上面类似小根堆的性质,我们可以倍增找出这些点的 LCA,然后就是套路地 dfs 序加上 RMQ了。

代码

// e3c8f1a924 2021年08月02日 星期一 13时59分36秒
#include<cstdarg>
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
using std::vector; using std::priority_queue; using std::pair; using std::make_pair; using std::swap; using std::min; using std::greater;
int _printf(char *format, ...) {
    va_list args; int k;
    va_start(args, format), printf("\033[34m"), k = vprintf(format, args), printf("\033[0m"), va_end(args);
    return k;
}
int _puts(char *str) { int k; return printf("\033[34m"), k = puts(str), printf("\033[0m"), k; }
int _putchar(int c) { int k; return printf("\033[34m"), k = putchar(c), printf("\033[0m"), k; }
#ifdef LOCAL
    #define printf _printf
    #define puts _puts
    #define putchar _putchar
#endif
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long ul;
typedef unsigned long long ull;

int T, n, m, cnt, f[400005], fa[400005][30], lt[400005], dfn[400005], lg[400005], siz[400005];
ll dis[400005], ST[400005][30];
vector<int> edge[200005], len[200005], son[400005];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int > > > q;
priority_queue<pair<int, pair<int, int> > > s;

void dijkstra(int s) {
    for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f3f3f3f3fll;
    dis[s] = 0, q.push(make_pair(0, s));
    while (!q.empty()) {
        pair<int, int> p = q.top(); q.pop();
        if (p.first != dis[p.second]) continue;
        int u = p.second;
        for (int i = 0, iBound = edge[u].size(); i < iBound; i++) {
            int v = edge[u][i], w = len[u][i];
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push(make_pair(dis[v], v));
        }
    }
}
int find(int u) { return f[u] == u ? u : (f[u] = find(f[u])); }
int check(int u, int v) { return find(u) == find(v); }
void merge(int u, int v) {
    int a = find(u), b = find(v);
    if (a < b) swap(a, b); f[b] = a;
}
void kruskal() {
    cnt = n; for (int i = 1; i < 2 * n; i++) f[i] = i, lt[i] = 0x3f3f3f3f;
    while (!s.empty()) {
        pair<int, pair<int, int> > p = s.top(); s.pop();
        int u = p.second.first, v = p.second.second, w = p.first;
        if (check(u, v)) continue;
        int a = find(u), b = find(v);
        cnt++, merge(a, cnt), merge(b, cnt), fa[a][0] = fa[b][0] = cnt, son[cnt].push_back(a), son[cnt].push_back(b), lt[cnt] = w;
        if (cnt == 2 * n - 1) break;
    }
    cnt = 0; while (!s.empty()) s.pop();
}
void dfs(int u) {
    dfn[u] = ++cnt, ST[cnt][0] = (u <= n ? dis[u] : 0x3f3f3f3f3f3f3f3fll), siz[u] = 1;
    for (int i = 0, iBound = son[u].size(); i < iBound; i++) dfs(son[u][i]), siz[u] += siz[son[u][i]];
}
void build() {
    for (int i = 1; i <= lg[2 * n - 1]; i++) {
        for (int j = 1; j + (1 << i) <= 2 * n; j++) ST[j][i] = min(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
        for (int j = 1; j < 2 * n; j++) fa[j][i] = fa[fa[j][i - 1]][i - 1];
    }
}
ll query(int a, int b) { int k = lg[b - a + 1]; return min(ST[a][k], ST[b - (1 << k) + 1][k]); }
ll ask(int u, int p) {
    int k = lg[2 * n - 1];
    while (!fa[u][k]) k--;
    while (~k) { while ((~k) && lt[fa[u][k]] <= p) k--; (~k) && (u = fa[u][k]); }
    return query(dfn[u], dfn[u] + siz[u] - 1);
}

int main() {
#ifndef LOCAL
    //freopen("return.in", "r", stdin);
    //freopen("return.out", "w", stdout);
#endif
    for (int i = 2; i <= 400000; i++) lg[i] = lg[i >> 1] + 1;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++) {
            int u, v, l, a; scanf("%d%d%d%d", &u, &v, &l, &a);
            edge[u].push_back(v), edge[v].push_back(u);
            len[u].push_back(l), len[v].push_back(l);
            s.push(make_pair(a, make_pair(u, v)));
        }
        dijkstra(1), kruskal(), dfs(2 * n - 1), build();
        int q, k, s; ll lans = 0; scanf("%d%d%d", &q, &k, &s);
        while (q--) {
            int v, p; scanf("%d%d", &v, &p);
            v = (v + k * lans - 1) % n + 1, p = (p + k * lans) % (s + 1);
            printf("%lld\n", lans = ask(v, p));
        }
        for (int i = 1; i <= n; i++) edge[i].clear(), len[i].clear();
        for (int i = 1; i < 2 * n; i++) son[i].clear();
    }
    return 0;
}