首页 题解

# Description

洛谷传送门

# Solution

KruskalKruskal 重构树好题。

我们先按照水位 aa，建 KruskalKruskal 重构树。具体来讲：按水位从高到低排序，每次选出剩余边中水位最高的一条边插入到树中，这样就建成了一个小根堆。

然后我们再来考虑询问。

对于一个水位线 pp，若 p<Kruskalp < Kruskal 重构树上的点 xx 的水位，那么在以 xx 为根的子树中，开车是可以随意通行的，对答案没有贡献。

若 p>t[x].depp > t[x].dep 且 p<t[fa[x]].depp < t[fa[x]].dep，那么它就不得不在点 fa[x]fa[x] 下车，所以对答案的贡献就是从 fa[x]fa[x] 到 1 的距离。

那这个距离该如何算呢？

这个很简单，只需要提前跑个 dijkstradijkstra 堆优化预处理一下即可，千万千万千万不要使用 spfaspfa （spfa 就是在这里死的 QwQ）

我们对于一组询问 vpv\ p，找到上述的 xx 节点即可。

现在的问题就是如何找到这样的节点，我们考虑倍增，倍增向上跳（就是个板子），具体见代码。

# Code

（UOJ 不干人事 hack 了 把 0x3f3f3f3f 作为无穷大，而且无穷大开 2e92e9 的话还得开 longlonglong \ long，所以这里放个洛谷能过的代码吧。）

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }
    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 4e5 + 10;
int T, n, m, lst;
struct node{
    int u, v, l, a, nxt;
    bool operator < (const node &b) const{
        return a > b.a;
    }
}edge[N << 1], e[N << 1], tmp[N << 1];
int head[N], tot;
inline void add(int x, int y, int l){
    edge[++tot].v = y, edge[tot].l = l, edge[tot].nxt = head[x];
    head[x] = tot;
}
struct Heap{
    int id, dis;
    bool operator < (const Heap &b) const{
        return dis > b.dis;
    }
};
int dis[N];
inline void dijkstra(){
    priority_queue <Heap> q;
    q.push((Heap){1, 0});
    memset(dis, 0x3f, sizeof(dis));
    dis[1] = 0;
    while(!q.empty()){
        Heap now = q.top();
        q.pop();
        int x = now.id;
        if(dis[x] < now.dis) continue;
        for(int i = head[x]; i; i = edge[i].nxt){
            int y = edge[i].v;
            if(dis[y] > dis[x] + edge[i].l){
                dis[y] = dis[x] + edge[i].l;
                q.push((Heap){y, dis[y]});
            }
        }
    }
}
int f[N];
int cnt;
vector <int> g[N];
inline int find(int x){
    return f[x] == x ? x : f[x] = find(f[x]);
}
inline void kruskal(){
    sort(e + 1, e + 1 + m);
    for(int i = 1; i <= n; ++i) f[i] = i;
    cnt = n;
    int num = 0;
    for(int i = 1; i <= m; ++i){
        int fu = find(e[i].u), fv = find(e[i].v);
        if(fu != fv){
            num++;
            tmp[++cnt].a = e[i].a;
            f[fu] = f[fv] = f[cnt] = cnt;
            g[cnt].push_back(fu), g[cnt].push_back(fv);
        }
        if(num == n - 1) break;
    }
}
int fa[N][20], dep[N];
inline void dfs(int x, int p){
    fa[x][0] = p, dep[x] = dep[p] + 1;
    for(int i = 1; i <= 19; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for(auto y : g[x])
        dfs(y, x), tmp[x].l = min(tmp[x].l, tmp[y].l);
}
inline int query(int x, int y){
    for(int i = 19; i >= 0; --i)
        if(dep[x] - (1 << i) > 0 && tmp[fa[x][i]].a > y)
            x = fa[x][i];
    return tmp[x].l;
}
inline void solve(){
    kruskal();
    dfs(cnt, 0);
    int q = read(), k = read(), s = read();
    while(q--){
        int u = (read() + k * lst - 1) % n + 1, p = (read() + k * lst) % (s + 1);
        write(lst = query(u, p)), puts("");
    }
}
inline void clear(){
    memset(head, 0, sizeof(head));
    memset(fa, 0, sizeof(fa));
    memset(tmp, 0, sizeof(tmp));
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= cnt; ++i) g[i].clear();
    tot = lst = 0;
}
int main(){
    T = read();
    while(T--){
        n = read(), m = read();
        for(int i = 1; i <= m; ++i){
            e[i].u = read(), e[i].v = read(), e[i].l = read(), e[i].a = read();
            add(e[i].u, e[i].v, e[i].l), add(e[i].v, e[i].u, e[i].l);
        }
        dijkstra();
        for(int i = 1; i <= n; ++i) tmp[i].l = dis[i];
        for(int i = (n + 1); i <= (n << 1); ++i) tmp[i].l = INF;
        solve(), clear();
    }
    return 0;
}
# End