好久没更新博客了……
说说本题，预处理出所有的dis[x]表示1至x的长度，询问(v,p)的答案为min_{minLev(x,v)>p} dis[x]。建立关于lev从大到小的kruskal重构树，则minlev(x,v)=val[lca(x,v)]。
换句话说，任意在重构树v的某个祖先d有val[d]>p，可以用d子树（除开包含v节点的儿子子树）中所有叶节点的最小dis来更新答案。
注意到重构树是个二叉树。因此对于关于d查询的子树仍是一个完整的子树结构，设为d'(d的某个儿子)。如果令mindis[x]表示子树x的叶节点的最小dis值，则直接拿mindis[d']来更新。
若p始终为-inf,可以自顶向下预处理上述值，转换到一般情况就可以考虑树上主席树了。\(%^#\)&^&…… 这么写就成笑话了……注意到满足d[v]>p的点集中分布在v的祖先链的前缀，可以倍增找出那个分界点(深度最小的val<=p的点)然后取它的mindis……
1A了开心?
参考实现
#include <bits/stdc++.h>
using namespace std;
const int N=8e5+10;struct Enode {int u,v,a,l;bool operator<(const Enode&d) const{return a>d.a;}
};
struct Pnode {int key,dis;bool operator<(const Pnode&d) const{return dis>d.dis;}
};int cnt,dis[N];
int head[N],to[N],len[N],lst[N];
bool vis[N];void ins(int x,int y,int w) {to[++cnt]=y,len[cnt]=w,lst[cnt]=head[x],head[x]=cnt;to[++cnt]=x,len[cnt]=w,lst[cnt]=head[y],head[y]=cnt;
}
priority_queue<Pnode> pq;
void dijkstra() {memset(dis,0x3f,sizeof dis);pq.push((Pnode){1,dis[1]=0});while(pq.size()) {int x=pq.top().key; pq.pop();if(vis[x]) continue; vis[x]=1;for(int i=head[x]; i; i=lst[i]) if(dis[to[i]]>dis[x]+len[i]) pq.push((Pnode){to[i],dis[to[i]]=dis[x]+len[i]});}
}Enode a[N];
int n,m,rt[N],val[N],ch[N][2];
int fa[N][20];int find(int x) {return rt[x]==x?x:rt[x]=find(rt[x]);}
void dfs(int x,int d) {for(int i=1; (1<<i)<=d; ++i) fa[x][i]=fa[fa[x][i-1]][i-1];if(x>n) {fa[ch[x][0]][0]=x; dfs(ch[x][0],d+1);fa[ch[x][1]][0]=x; dfs(ch[x][1],d+1);dis[x]=min(dis[ch[x][0]],dis[ch[x][1]]);}
}void rebuild() {int tot=n;sort(a+1,a+m+1); for(int i=1; i<=n; ++i) {memset(fa[i],0,sizeof fa[i]);rt[i]=i;}for(int i=1; i<=m; ++i) {int x=find(a[i].u),y=find(a[i].v);if(x!=y) {tot++; memset(fa[tot],0,sizeof fa[tot]);rt[tot]=tot; val[tot]=a[i].a;rt[ch[tot][0]=x]=rt[ch[tot][1]=y]=tot;}}dfs(tot,1);
}
int query(int x,int p) {for(int i=19; ~i; --i) if(fa[x][i]&&val[fa[x][i]]>p) x=fa[x][i];return dis[x];
}int main() {int T;scanf("%d",&T);while(T--) {cnt=0;memset(vis,0,sizeof vis);memset(head,0,sizeof head);scanf("%d%d",&n,&m);for(int i=1; i<=m; ++i) {scanf("%d%d%d%d",&a[i].u,&a[i].v,&a[i].l,&a[i].a);ins(a[i].u,a[i].v,a[i].l);}dijkstra();rebuild();int Q,K,S,lans=0;scanf("%d%d%d",&Q,&K,&S);for(int v,p; Q--; ) {scanf("%d%d",&v,&p);v=(v+K*lans-1)%n+1;p=(p+K*lans)%(S+1);lans=query(v,p);printf("%d\n",lans);}}return 0;
}