题目传送门(BZOJ)
>原文链接<

题解 :

  • 同步赛想不出来, 学长让我去学重构树, 学完之后发现这题真的水 (如果不包括数组开小的RE的话是1A的
  • 没写过重构树的请看一下重构树

以下是正文


对原图跑一遍从1开始的最短路, 这样我们每次询问就是求所有从$S$不过水能到的所有点中的距离最小值.

Kruskal求最大生成树(边权按海拔排序), 对其进行重构.

对于一次查询重构树中的点$v$,若它的一个祖先$fa$满足$val[fa] > p$, 则可以到达$fa$子树的所有叶子节点

我们要求的答案就是$fa$的子树最小值

所以我们按老套路倍增找到$fa$,另外, 在处理询问之前要先做一个简单的树形DP, 预处理出子树最小值

答案就是$dis[fa]$(本来$dis$是处理不到$fa$的, 但可以直接用它当DP的数组)

注意 : 多组数据之间不光要清数组, 还要重置lastans

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define mp make_pair#define ms(a) memset(a, 0, sizeof a)#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000], *p1, *p2; const int N = 400001;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}char pbuf[100000],*pp=pbuf;void push(const char c) { if(pp-pbuf==100000) fwrite(pbuf,1,100000,stdout),pp=pbuf; *pp++=c;}void write(int x) { static int sta[35]; int top=0; do{sta[top++]=x%10,x/=10;}while(x); while(top) push(sta[--top]+'0');}int fa[N], dis[N], f[20][N], vis[N];int n, m, Q, K, S, ans, val[N];struct Data { int u, v, l, a; inline bool operator < (const Data &A) const { return a > A.a; }}e1[N<<2];struct Edge { int to, val; Edge *next;}*h[N], e[N<<2];int _;inline void addEdge(int u, int v, int w = 0) { Edge * tmp = &e[++_]; tmp->to = v; tmp->val = w; tmp->next = h[u]; h[u] = tmp;}struct getDis { priority_queue<pair<int, int> > q; inline void Init() { _ = 0; ms(h); for(int i = 1; i <= m; i ++ ) { int u = e1[i].u, v = e1[i].v, w = e1[i].l; addEdge(u, v, w); addEdge(v, u, w); } } void Dijkstra() { ms(vis); memset(dis, 0x3f, sizeof dis); dis[1] = 0; q.push(mp(0, 1)); while(!q.empty()) { int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; rev(i, u) if(dis[i->to] > dis[u]+i->val) { dis[i->to] = dis[u]+i->val; q.push(mp(-dis[i->to], i->to)); } } }}Dijkstra;struct Kruskal_Rebuild_Tree { inline void Init() { _ = 0; ms(h); } int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);} void Build_Tree() { for(int i = 1; i < n << 1; i ++ ) fa[i] = i; int cnt = n; sort(e1+1, e1+m+1); for(int i = 1; i <= m; i ++ ) { int dx = find(e1[i].u), dy = find(e1[i].v); if(dx != dy) { fa[dx] = fa[dy] = ++cnt; f[0][dx] = f[0][dy] = cnt; val[cnt] = e1[i].a; addEdge(cnt, dx), addEdge(cnt, dy); if(cnt == 2*n-1) break; } } }}KRT;struct getAns { void dfs(int p) { for(int i = 1; i < 20; i ++ ) f[i][p] = f[i-1][f[i-1][p]]; rev(i, p) if(i->to != f[0][p]) { dfs(i->to); dis[p] = min(dis[p], dis[i->to]); } } void Solve() { Q = rd(), K = rd(), S = rd(); while(Q -- ) { int v = (rd()+K*ans-1)%n+1, p = (rd()+K*ans)%(S+1); int u = v; for(int i = 19; ~i; i -- ) if(val[f[i][u]] > p) u = f[i][u]; write(ans = dis[u]); push('\n'); } }}Solve;inline void init() { ms(f); ans = 0;}int main() { int T = rd(); while(T -- ) { init(); n = rd(), m = rd(); for(int i = 1; i <= m; i ++ ) { e1[i].u = rd(), e1[i].v = rd(), e1[i].l = rd(), e1[i].a = rd(); } Dijkstra.Init(); Dijkstra.Dijkstra(); KRT.Init(); KRT.Build_Tree(); Solve.dfs(2*n-1); Solve.Solve(); } fwrite(pbuf,1,pp-pbuf,stdout);}