// Kruskal 重构树 O(MlogM+NlogN)
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

int read(){
  int f=1,x=0; char c=getchar();
  while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
  while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
  return f*x;
}
const int N=800005;
int idx,h[N],to[N],ne[N],ww[N]; //边权为长度
void add(int u,int v,int w){
  to[++idx]=v;ww[idx]=w;ne[idx]=h[u];h[u]=idx;
}
struct E{int u,v,hi;}e[N]; //边权为海拔
int n,m,cnt,val[N]; //val新建点点权
int d[N],vis[N];
int pa[N],fa[N][20];

void dijkstra(){ //预处理1到所有节点的最短路
  memset(vis,0,sizeof vis);
  memset(d,0x3f,sizeof d); d[1]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q; //小根堆
  q.push({0,1});
  while(!q.empty()){
    auto u=q.top().second; q.pop();
    if(vis[u])continue; vis[u]=1;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
      }
    }
  }
}
int find(int x){ //并查集查找
  return pa[x]==x?x:pa[x]=find(pa[x]);
}
void kruskal(){ //重构树
  memset(h,0,sizeof(h)); idx=1;
  sort(e+1,e+1+m,[&](E a,E b){return a.hi>b.hi;});
  for(int i=1;i<=n;++i)pa[i]=i; 
  for(int i=1;i<=m;i++){
    int fu=find(e[i].u), fv=find(e[i].v);
    if(fu!=fv){
      val[++cnt]=e[i].hi;
      pa[fu]=pa[fv]=pa[cnt]=cnt;
      add(cnt,fu,0); add(cnt,fv,0);
    }
  }
}
void dfs(int u,int f){ //预处理 d,fa
  fa[u][0]=f;
  for(int i=1;i<=19;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
  for(int i=h[u];i;i=ne[i]){
    int v=to[i];
    dfs(v,u);
    d[u]=min(d[u],d[v]); //更新那些新建点到1的最短距离
  }
}
int main(){
  int T=read();
  while(T--){
    memset(h,0,sizeof(h)); idx=1;
    memset(fa,0,sizeof(fa)); 
    memset(d,0x3f,sizeof(d));
    
    n=read();m=read();cnt=n; //cnt新建点
    for(int i=1;i<=m;i++){
      int u=read(),v=read(),w=read(),hi=read();
      add(u,v,w); add(v,u,w);
      e[i]={u,v,hi};
    }
    dijkstra(); //预处理1到所有节点的最短路
    kruskal();  //重构树
    dfs(cnt,0); //预处理 d,fa

    int Q=read(),K=read(),S=read();
    for(int last=0;Q--;){
      int v=read(),p=read();
      v=(v+K*last-1)%n+1;
      p=(p+K*last)%(S+1);
      for(int j=19;j>=0;--j) //倍增找到深度最小且海拔大于水位的节点
        if(fa[v][j] && val[fa[v][j]]>p) v=fa[v][j];
      printf("%lld\n",last=d[v]);
    }
  }
}

$$\Large\texttt{My Blog}$$

题目链接：Luogu 4768

魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图。我们依次用 $l,a$ 描述一条边的长度、海拔。

作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。

我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。

Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天，每一天 Yazid 都会告诉你他的出发点 $v$ ，以及当天的水位线 $p$。

每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

需要特殊说明的是，第二天车会被重置，这意味着：

• 车会在新的出发点被准备好。
• Yazid 不能利用之前在某处停放的车。

Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

注意：本题有多组数据，并且强制在线！

数据范围：$T\le 3$，$n\le 2\times 10^5$，$m,Q\le 4\times 10^5$，$l\le 10^4$，$a\le 10^9$

Solution

我们先分析一下询问的本质：将 $1$ 到 $v$ 的路径分成两个部分，一段全部开始，后一段全部走路。那我们可以枚举一个断点 $u$，在满足 $u$ 到 $v$ 的路径上所有的边的海拔都大于 $p$ 的情况下，要求 $1$ 到 $u$ 的最短路最短。

我们怎么求出从 $v$ 出发可以到达的点呢？这些点显然满足从 $v$ 出发，路径上所有边的海拔都大于 $p$。由此可以想到，这些路径一定在原图的最大生成树上！

至此，已经可以发现能用 $\texttt{Kruskal}$ 重构树求解了。关于 $\texttt{Kruskal}$ 重构树的求法，请见「算法笔记」Kruskal 重构树。

我们把每条边按照海拔降序排列，求出关于海拔的最大生成树。由于这样的重构树是一个小根堆（每个节点子树内的所有节点的点权都不小于该节点），对于每次询问求出包含 $v$ 的子树中根节点深度最小并且海拔（点权）大于 $p$ 的子树 $x$，那么 $x$ 子树内的所有节点都可以由 $v$ 开车到达！

求解深度最小的满足条件的节点，可以直接用树上倍增解决，这个倍增数组可以在 $\texttt{Kruskal}$ 的过程中求出来。

现在，这棵子树内的所有点都可以作为上文所说的断点，我们只需要求出子树内的点到点 $1$ 的最短距离的最小值。我们可以预处理每个点到 $1$ 的最短距离，然后对于每棵子树求个 $\min$ 即可。由于重构树的求解过程中我们可以知道这棵树的形态，所以这个取 $\min$ 的过程不需要 $\texttt{DFS}$，而是可以直接在 $\texttt{Kruskal}$ 中完成！

时间复杂度：$O(T\cdot n\log n)$（此处认为 $n,m,Q$ 三者同阶）

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
typedef std::pair<int,int> pii;
#define mk std::make_pair
inline char nc() {
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
template <class Tp> inline void read(register Tp &s) {
    s=0;char c=nc();for(;c<'0'||c>'9';c=nc());for(;c>='0'&&c<='9';s=s*10+(c^48),c=nc());
}

const int N=4e5+5,M=8e5+5,logN=19+1;
int n,m,tot,lnk[N],ter[M],nxt[M],val[M],fa[N],f[N][logN],dis[N],hei[N];
bool vis[N];
struct Edge {
    int u,v,h;
    bool operator < (const Edge &rhs) const {
        return h>rhs.h;
    }
}e[M];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],val[tot]=w,lnk[u]=tot;
}
void input() {
    tot=0,memset(lnk,0,sizeof(lnk));
    read(n),read(m);
    for(int i=1;i<=m;++i) {
        int u,v,w,h;
        read(u),read(v),read(w),read(h);
        add(u,v,w),add(v,u,w);
        e[i].u=u,e[i].v=v,e[i].h=h;
    }
}
void dijkstra(int s) {
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
    q.push(mk(dis[s]=0,s));
    while(!q.empty()) {
        int u=q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(dis[v]>dis[u]+val[i]) {
                dis[v]=dis[u]+val[i];
                if(!vis[v]) q.push(mk(dis[v],v));
            }
        }
    }
}
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void exKruskal() {
    std::sort(e+1,e+m+1);
    for(int i=1;i<=n+n;++i) fa[i]=i;
    int idx=n;
    for(int i=1;i<=m;++i) {
        int fu=find(e[i].u),fv=find(e[i].v);
        if(fu==fv) continue;
        fa[fu]=fa[fv]=++idx,hei[idx]=e[i].h;
        dis[idx]=std::min(dis[fu],dis[fv]);
        f[fu][0]=f[fv][0]=idx;
    }
    for(int j=1;(1<<j)<=idx;++j) for(int i=1;i<=idx;++i) f[i][j]=f[f[i][j-1]][j-1];
}
int query(int u,int p) {
    for(int i=19;~i;--i) if(f[u][i]&&hei[f[u][i]]>p) u=f[u][i];
    return dis[u];
}
void solve() {
    int q,k,s;
    read(q),read(k),read(s);
    int lastans=0;
    while(q--) {
        int v,p;
        read(v),read(p);
        v=(v+k*lastans-1)%n+1;
        p=(p+1LL*k*lastans)%(s+1);
        printf("%d\n",lastans=query(v,p));
    }
}
int main() {
    int T;
    for(scanf("%d",&T);T--;) {
        input();
        dijkstra(1);
        exKruskal();
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 2e5 + 10, M = 4e5 + 10;
struct Edge { int x, y, l, a; } E[M];
vector<PII> G1[N];
vector<int> G2[N << 1];
int T, n, nn, m, Q, K, S, lastans, v, p;
int dis[M], a[M], fa[M], f[M][25], dep[M], D, val[M];
bool vis[N];

void qr(int &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + c - '0';
    if (f == -1) x = -x;
}

void dijkstra() {    
    memset(dis, 0x3f, sizeof(dis)); dis[1] = 0;
    memset(vis, 0, sizeof(vis));
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    while (!q.empty()) {
        int x = q.top().second; q.pop(); if (vis[x]) continue;
        vis[x] = 1;
        for (auto [y, w] : G1[x])
            if (dis[y] > dis[x] + w) dis[y] = dis[x] + w, q.push({dis[y], y});
    }
}

int findfa(int x) { return x == fa[x] ? x : fa[x] = findfa(fa[x]); }

void dfs(int x, int ff) {
    dep[x] = dep[ff] + 1;
    f[x][0] = ff; for (int i = 1; i <= D; i++) f[x][i] = f[f[x][i-1]][i-1];
    for (int y : G2[x]) {
        dfs(y, x);
        dis[x] = min(dis[x], dis[y]);
    }
}

void ex_kruskal() {
    for (int i = 1; i <= 2 * n; i++) fa[i] = i;
    sort(E + 1, E + m + 1, [&](Edge e1, Edge e2) { return e1.a > e2.a; });
    memset(G2, 0, sizeof(G2));
    nn = n;
    for (int i = 1; i <= m; i++) {
        int tx = findfa(E[i].x), ty = findfa(E[i].y);
        if (tx != ty) {
            nn++;
            val[nn] = E[i].a;
            fa[tx] = fa[ty] = nn;
            G2[nn].emplace_back(tx);
            G2[nn].emplace_back(ty);
        }
        if (nn == 2 * n - 1) break;
    }
}

int query(int x, int p) {
    for (int i = D; i >= 0; i--) if (dep[f[x][i]] >= dep[nn] && val[f[x][i]] > p) x = f[x][i];	
    return dis[x];
}

int main() {
    qr(T); 
    while (T--) {
        qr(n); qr(m);
        memset(G1, 0, sizeof(G1));
        for (int i = 1; i <= m; i++) {
            qr(E[i].x), qr(E[i].y), qr(E[i].l), qr(E[i].a);
            G1[E[i].x].emplace_back(PII(E[i].y, E[i].l));
            G1[E[i].y].emplace_back(PII(E[i].x, E[i].l));
        }
        dijkstra();
        ex_kruskal();
        dep[nn] = 0; D = log2(2 * n); dfs(nn, 0);
        qr(Q), qr(K), qr(S); lastans = 0;
        while (Q--) {
            qr(v); qr(p);
            v = (v + K * lastans - 1) % n + 1;
            p = (p + K * lastans) % (S + 1);
            lastans = query(v, p);
            printf("%d\n", lastans);
        }
    }
    return 0;
}