题目描述
本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个
n
n
n 个节点、
m
m
m 条边的无向连通图（节点的编号从
1
1
1 至
n
n
n）。我们依次用
l
,
a
l,a
l,a 描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免 的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他 温暖的家。 Yazid 的家恰好在魔力之都的
1
1
1 号节点。对于接下来
Q
Q
Q 天，每一天Yazid 都会告诉你他的出发点
v
v
v，以及当天的水位线
p
p
p。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：
车会在新的出发点被准备好。 Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 本题强制在线。
n
≤
2
×
1
0
5
n\le 2\times 10^5
n≤2×105，
m
≤
4
×
1
0
5
m\le 4\times 10^5
m≤4×105，
Q
≤
4
×
1
0
5
Q\le 4\times 10^5
Q≤4×105，
l
≤
1
0
4
l\le 10^4
l≤104，
a
≤
1
0
9
a\le 10^9
a≤109。
算法分析
Dijkstra+Kruskal 重构树+倍增+DFS序+线段树。
和 【BZOJ 3551】Peaks 加强版 一样，先构出 Kruskal 求最大生成树的重构树，可以下车的位置就在一个子树内了，事先预处理出每个点到出发点的最短路，DFS 序+线段树维护子树区间范围最小值即可。
代码实现
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
#include <vector>
#include <functional>
#include <algorithm>
typedef std
::pair
<int,int> P
;
const int maxn
=(int)2e5+5;
const int maxm
=(int)4e5+5;
char buf
[1<<15],*fs
=buf
,*ft
=buf
;
inline char gc() {
if(fs
==ft
) {
ft
=(fs
=buf
)+fread(buf
,1,1<<15,stdin);
if(fs
==ft
) return 0;
}
return *fs
++;
}
inline void read(int &num
) {
char c
=gc();int f
=false;num
=0;
while(c
<'0'||'9'<c
) {if(c
=='-') f
=true;c
=gc();}
while('0'<=c
&&c
<='9') {num
=num
*10+c
-'0';c
=gc();}
if(f
) num
=-num
;
}
struct edge
{int u
,v
,w
;} e
[maxm
],edges
[maxm
<<1];
int head
[maxn
<<1],nxt
[maxm
<<1],idx
=0;
inline void clear() {idx
=0;memset(head
,0,sizeof(head
));}
inline void add(int u
,int v
,int w
=0) {
edges
[++idx
]=(edge
){u
,v
,w
};
nxt
[idx
]=head
[u
];head
[u
]=idx
;
}
inline bool cmp(const edge
&x
,const edge
&y
) {return x
.w
>y
.w
;}
int fa
[maxn
<<1];int find(int x
) {return x
==fa
[x
]?x
:fa
[x
]=find(fa
[x
]);}
int d
[maxn
<<1],h
[maxn
<<1],pa
[maxn
<<1][20],tot
[maxn
<<1],dfn
[maxn
<<1],dl
[maxn
<<1],dfsidx
=0;
void dfs(int x
) {
tot
[x
]=1;dl
[dfn
[x
]=++dfsidx
]=x
;
for(register int i
=head
[x
];i
;i
=nxt
[i
]) {int v
=edges
[i
].v
;dfs(v
);tot
[x
]+=tot
[v
];}
}
int min
[maxn
<<5];
inline void build(int o
,int l
,int r
) {
int mid
=(l
+r
)>>1;
if(l
==r
) min
[o
]=d
[dl
[mid
]];
else {
build(o
<<1,l
,mid
);build(o
<<1|1,mid
+1,r
);
min
[o
]=std
::min(min
[o
<<1],min
[o
<<1|1]);
}
}
inline int query(int o
,int l
,int r
,int ql
,int qr
) {
int mid
=(l
+r
)>>1;
if(ql
<=l
&&r
<=qr
) return min
[o
];
int ans
=0x7fffffff;
if(ql
<=mid
) ans
=std
::min(ans
,query(o
<<1,l
,mid
,ql
,qr
));
if(mid
+1<=qr
) ans
=std
::min(ans
,query(o
<<1|1,mid
+1,r
,ql
,qr
));
return ans
;
}
int main() {
int t
;scanf("%d",&t
);
while(t
--) {
int n
,ln
,m
;read(n
);read(m
);ln
=n
;
int u
,v
,l
,a
;clear();
for(register int i
=0;i
<m
;++i
) {
read(u
);read(v
);read(l
);read(a
);
add(u
,v
,l
);add(v
,u
,l
);e
[i
]=(edge
){u
,v
,a
};
}
std
::priority_queue
<P
,std
::vector
<P
>,std
::greater
<P
> > pq
;
memset(d
,0x3f,sizeof(d
));d
[1]=0;pq
.push(P(0,1));
while(pq
.size()) {
P x
=pq
.top();pq
.pop();int u
=x
.second
;
if(d
[u
]^x
.first
) continue;
for(register int i
=head
[u
];i
;i
=nxt
[i
]) {
edge
&e
=edges
[i
];
if(d
[e
.v
]>d
[u
]+e
.w
) {
d
[e
.v
]=d
[u
]+e
.w
;
pq
.push(P(d
[e
.v
],e
.v
));
}
}
}
std
::sort(e
,e
+m
,cmp
);clear();
for(int i
=1;i
<=(n
<<1);++i
) fa
[i
]=i
;
for(register int i
=0;i
<m
;++i
) {
int x
=find(e
[i
].u
),y
=find(e
[i
].v
);if(x
==y
) continue;
pa
[x
][0]=pa
[y
][0]=fa
[x
]=fa
[y
]=++n
;h
[n
]=e
[i
].w
;add(n
,x
);add(n
,y
);
}
for(register int i
=1;i
<20;++i
) for(register int x
=1;x
<=n
;++x
) pa
[x
][i
]=pa
[pa
[x
][i
-1]][i
-1];
dfsidx
=0;dfs(n
);build(1,1,n
);
int q
,k
,s
,v0
,p0
,la
=0;read(q
);read(k
);read(s
);
while(q
--) {
read(v0
);read(p0
);v0
=(v0
+k
*la
-1)%ln
+1;p0
=(p0
+k
*la
)%(s
+1);
for(register int i
=19;i
>=0;--i
) if(pa
[v0
][i
]&&h
[pa
[v0
][i
]]>p0
) v0
=pa
[v0
][i
];
printf("%d\n",la
=query(1,1,n
,dfn
[v0
],dfn
[v0
]+tot
[v0
]-1));
}
}
return 0;
}
