题目概述

给出 $n$ 个点 $m$ 条无向边的连通图，每条边有距离和高度，如果高度 $\le$ 水的高度这条边就会被淹没，令 $dis_i$ 表示到达 $1$ 号点的最短路，问从 $x$ 点出发水位为 $p$ 时，$min\{dis_y|x\to y\}$ 。

解题报告

本来以为可持久化并查集会被卡，结果过了，那我还作死继续想更好的解法（也没想出什么）。

不过的确有更好地解法：Kruskal重构树。我们按照高度做最大生成树，构造Kruskal重构树，由于 $Kruskal$ 是小根堆，那么每次查询的时候只需要知道 $x$ 最多向上走到 $y$ ，然后输出 $y$ 子树中最小的 $dis$ 。

好像和上次的写法不一样……毕竟这道题要找子树……所以每次合并的时候要新建点表示边，然后连向这个新点。

示例程序

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#include <ext/pb_ds/priority_queue.hpp>
#define fr first
#define sc second
#define mp make_pair
#define X fr.fr
#define Y fr.sc
#define L sc.fr
#define H sc.sc
using namespace std;using namespace __gnu_pbds;typedef pair<pair<int,int>, pair<int,int> > Edge;
typedef __gnu_pbds::priority_queue<pair<int,int>,greater< pair<int,int> >,pairing_heap_tag> Heap;
const int maxn=400000,maxm=400000,Log=19;

int T,n,N,m,te,K,S,lstans,dis[maxn+5],fat[maxn+5],W[maxn+5],ST[maxn+5][Log+5];Edge e[maxm+5];
int E,lnk[2][maxn+5],son[(maxm<<1)+maxn+5],nxt[(maxm<<1)+maxn+5],w[(maxm<<1)+maxn+5];
Heap que;Heap::point_iterator it[maxn+5];bool vis[maxn+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
    if (l==r) return EOF;return *l++;
}
inline int readi(int &x){
    int tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return (lst=='-'?x=-tot:x=tot),Eoln(ch);
}
inline void Add(int x,int y,int z) {son[++E]=(y);w[E]=z;nxt[E]=lnk[0][x];lnk[0][x]=E;}
inline void Add(int x,int y) {son[++E]=(y);nxt[E]=lnk[1][x];lnk[1][x]=E;}
inline void Dij(){
    while (!que.empty()) que.pop();for (int i=1;i<=n;i++) it[i]=0,vis[i]=false;
    for (int i=1;i<=(n<<1);i++) dis[i]=2e9;dis[1]=0;it[1]=que.push(mp(0,1));vis[1]=true;
    while (!que.empty()){
        int x=que.top().sc;que.pop();vis[x]=false;
        for (int j=lnk[0][x];j;j=nxt[j])
            if (dis[x]+w[j]<dis[son[j]]){
                dis[son[j]]=dis[x]+w[j];
                if (vis[son[j]]) que.modify(it[son[j]],mp(dis[son[j]],son[j]));
                else it[son[j]]=que.push(mp(dis[son[j]],son[j])),vis[son[j]]=true;
            }
    }
}
inline bool cmp(const Edge &a,const Edge &b) {return a.H>b.H;}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
void Dfs(int x,int pre=0){
    ST[x][0]=pre;for (int j=1;j<=Log;j++) ST[x][j]=ST[ST[x][j-1]][j-1];
    for (int j=lnk[1][x];j;j=nxt[j]) Dfs(son[j],x),dis[x]=min(dis[x],dis[son[j]]);
}
inline void AMOD(int &x,int tem,int MOD) {if ((x+=tem)>=MOD) x-=MOD;}
inline int Find(int x,int p) {for (int j=Log;~j;j--) if (ST[x][j]&&W[ST[x][j]]>p) x=ST[x][j];return dis[x];}
int main(){
    freopen("return.in","r",stdin);freopen("return.out","w",stdout);
    for (readi(T);T;T--){
        readi(n);N=n;readi(m);E=0;memset(lnk,0,sizeof(lnk));
        for (int i=1;i<=m;i++){
            readi(e[i].X);readi(e[i].Y);readi(e[i].L);readi(e[i].H);
            Add(e[i].X,e[i].Y,e[i].L);Add(e[i].Y,e[i].X,e[i].L);
        }Dij();for (int i=1;i<=(n<<1);i++) fat[i]=i,W[i]=-1;sort(e+1,e+1+m,cmp);
        for (int i=1;i<=m;i++){
            int x=getfa(e[i].X),y=getfa(e[i].Y);if (x==y) continue;
            W[++n]=e[i].H;Add(n,x);Add(n,y);fat[x]=fat[y]=n;
        }readi(te);readi(K);readi(S);
        for (Dfs(n),lstans=0;te;te--){
            int x,p;readi(x);readi(p);x--;AMOD(x,K?lstans%N:0,N);x++;AMOD(p,K?lstans%(S+1):0,S+1);
            printf("%d\n",lstans=Find(x,p));
        }
    }
    return 0;
}