前言

最近一场div2没开出C2，猛掉104分。
赛后补E，发现自己连E1都没思路，一问才知道是kruskal重构树。
好吧，OI时期欠下的债该还了。

kruskal重构树是什么

1. 它是一棵 $2n-1$ 个点的二叉树。点有点权，下面记作 $va{l}_x$。
2. 它是一个 大/小根堆，如果是最小生成树构建的就是大根堆，反之，如果是最大生成树构建的就是小根堆。
3. 对于原图上的每一对点 $(x,y)$，他们之间的最小/大边权是 $va{l}_{x,y}$，如果是最小生成树那就是最小边权，反之亦然。
4. 重构树所有叶子都是原图上的点，其他的点都不是原图上的点。
5. 如果原图不连通，你会得到一个重构树森林。

算法流程

1. 把边按照边权排序。
2. 初始化并查集。注意重构树有 $2n-1$ 个点，所以要开一个大小为 $2n-1$ 的并查集。
3. 设 $rt$ 为当前最大的点的编号，初始化 $rt=n$
4. 和 kruskal 一样，按顺序枚举边，如果两个点属于同一个集合就 continue，令 $u=getfather(x),v=getfather(y)$
5. 令 $rt++$，$f{a}_u=f{a}_v=rt$，$va{l}_{rt}=w_{x,y}$。也就是新建一个点作为 u 和 v 的父亲，并令它的点权等于边权。

例题

[NOI2018] 归程

思路

毫无疑问，我们肯定要预处理所有点到 1 号点的最短路。
如果是在最大生成树上跑的话，你会发现根本没法做。
考虑根据海拔建 kruskal 重构树。对于一个点 u，如果 $va{l}_u>p$ 且 $va{l}_{f{a}_u}\le p$，那么 $u$ 子树内的所有点都是可以不花任何代价互相到达的。于是我们需要预处理子树内的点到达 1 号点的最短距离，dfs即可。
对于一个出发点 $v$，我们需要找到最后一个没有被淹没的祖先，用倍增即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353,S=21;
vector<vector<int>> e,f;
vector<vector<array<int,2>>> E;
vector<int> val,dis,fa;
int n,m;
int gf(int x)
{return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void dij()
{priority_queue<array<int,2>,vector<array<int,2>>,greater<array<int,2>>> q;q.push({0,1});dis.assign(2*n,inf);dis[1]=0;vector<int> vis(n+1);while(!q.empty()){int u=q.top()[1]; q.pop();if(vis[u]) continue;vis[u]=1;for(auto [v,w]:E[u]){if(vis[v]||dis[u]+w>=dis[v])continue;dis[v]=dis[u]+w;q.push({dis[v],v});}}
}
void dfs(int u,int fa)
{f[u][0]=fa;for(int j=1; j<S; j++){f[u][j]=f[f[u][j-1]][j-1];}for(auto v:e[u]){dfs(v,u);dis[u]=min(dis[u],dis[v]);}
}
int query(int u,int p)
{for(int i=S-1; i>=0; i--){if(val[f[u][i]]>p)u=f[u][i];}return dis[u];
}
void O_o()
{cin>>n>>m;e.assign(n*2,vector<int>());val.assign(n*2,0);vector<array<int,4>> edge;//a,l,u,vE.assign(n+1,vector<array<int,2>>());for(int i=1; i<=m; i++){int u,v,l,a;cin>>u>>v>>l>>a;E[u].push_back({v,l});E[v].push_back({u,l});edge.push_back({a,l,u,v});}dij();sort(edge.begin(),edge.end(),greater<>());fa.assign(2*n,0);for(int i=1; i<=n*2-1; i++) fa[i]=i;int rt=n;for(auto [a,l,x,y]:edge){int u=gf(x),v=gf(y);if(u==v) continue;rt++;fa[u]=rt;fa[v]=rt;e[rt].push_back(u);e[rt].push_back(v);val[rt]=a;}f.assign(2*n,vector<int>(21,0));dfs(rt,0);int Q,K,S;cin>>Q>>K>>S;int ans=0;while(Q--){int v,p;cin>>v>>p;v=(v+K*ans-1)%n+1;p=(p+K*ans)%(S+1);ans=query(v,p);cout<<ans<<"\n";}
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;while(T--){O_o();}
}