目录
显示
题目链接
https://www.luogu.com.cn/problem/P4768
题解
本题需要用到一个叫 Kruskal 重构树 的东西。
我们首先分析一下这道题：首先给出一个 \(v\)，我们需要找到一条 \(v \to p \to 1\) 的路径，满足：
- \(v \to p\) 的路径全程没有积水（海拔高于水位线）；
- \(p \to 1\) 的路径尽可能短。
先解决第二部分。因为图是无向图，所以我们先预处理出 \(1\) 为起点的单源最短路径（记得不要用某死去的算法）。
对于第一部分，我们需要找到任意两点间海拔最低的边最高的一条路径，这个可以通过建立以海拔为边权的最大生成树解决（还记得最大/小生成树一定是瓶颈生成树吗？）。
接下来 Kruskal 重构树就要登场了。
我们在最大生成树上建立重构树，这棵树具有这样的特点：从 \(u\) 到 \(v\) 要经过的最低海拔，正是 \(\text{lca}(u,v)\) 的点权。而且，这棵树还是个小根堆。
也就是说，设水位线为 \(p\)，如果 \(u\) 的某个祖先 \(x\) 的点权大于 \(p\)，\(u\) 就可以抵达 \(x\) 的所有子节点。
因此我们只需要在所有可以到达的点中，找到距离 \(1\) 号点最近的点即可。
具体来说，我们从根节点开始遍历重构树，遍历到点 \(u\) 的时候，预处理 \(u\) 的子树中到 \(1\) 号点的最短距离。
对于一个起点 \(v\)，我们只需倍增向上跳，找到能到达的深度最小的祖先 \(pa\) 即可，则答案就是 \(pa\) 的子树中到 \(1\) 号点的最短距离。
这样我们就完美解决了本题。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
struct edge
{
int v,w,next;
}e[800005];
struct node
{
int u,v,l,a;
bool operator<(const node&p)const
{
return a>p.a;
}
}p[400005];
struct dsu
{
int fa[400005];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void set(int x,int y)
{
fa[x]=y;
}
}d;
int head[200005],dis[200005],vis[200005];
int cnt,n,m;
int val[400005],fa[400005][25],mind[400005],dep[400005];
vector<int> tr[400005];
void addedge(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
void dijkstra()
{
priority_queue<pii,vector<pii>,greater<pii> > q;
memset(dis,63,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
q.push(make_pair(0,1));
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
q.push(make_pair(dis[v],v));
}
}
}
}
void build_retree()
{
memset(val,0,sizeof(val));
for(int i=1;i<=2*n;i++)
{
tr[i].clear();
if(i<=n)mind[i]=dis[i];
else mind[i]=1<<30;
}
cnt=n;
sort(p+1,p+m+1);
d.init(2*n);
for(int i=1;i<=m;i++)
{
int u=p[i].u,v=p[i].v;
int fu=d.find(u),fv=d.find(v);
if(fu!=fv)
{
cnt++;
val[cnt]=p[i].a;
d.set(fu,cnt);
d.set(fv,cnt);
tr[cnt].push_back(fu);
tr[cnt].push_back(fv);
}
}
}
void dfs(int u,int f)
{
dep[u]=dep[f]+1;
fa[u][0]=f;
for(int i=1;i<=20;i++)
fa[u][i]=fa[fa[u][i-1]][i-1];
for(auto v:tr[u])
{
dfs(v,u);
mind[u]=min(mind[u],mind[v]);
}
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cnt=0;
memset(head,0,sizeof(head));
memset(dep,0,sizeof(dep));
memset(fa,0,sizeof(fa));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>p[i].u>>p[i].v>>p[i].l>>p[i].a;
addedge(p[i].u,p[i].v,p[i].l);
addedge(p[i].v,p[i].u,p[i].l);
}
dijkstra();
build_retree();
dfs(cnt,0);
int Q,K,S,lastans=0;
cin>>Q>>K>>S;
while(Q--)
{
int v,p;
cin>>v>>p;
v=(v+K*lastans-1)%n+1;
p=(p+K*lastans)%(S+1);
for(int i=20;i>=0;i--)
if(dep[v]>(1<<i)&&val[fa[v][i]]>p)v=fa[v][i];
cout<<(lastans=mind[v])<<endl;
}
}
return 0;
}