传送门
这道题是一道非常好的Kurskal重构树入门题。
题目中“两点间存在一条边没有被淹没”等价于“存在一条路径，其最小边权（最低海拔）大于水位线”。有一个很显然的贪心策略，就是每次尝试加入边权大的边，直到两点连通；此时加入的边就是当前两点路径的最小值，也就是“最小边权”的最大值。如果这个最大值都小于等于当前海拔，那么所有两点间的路径一定都会被淹没。
这个过程等价于构造一棵最大生成树。而第一个使得两点连通的加入边就是我们需要求的“最小边权最大值”。
如何才能维护这些值呢？事实上，我们可以将这些值都变成一个个节点。当每次往生成树中加入一条边时，我们就将边的端点同时接到一个父节点上，父节点的点权为这条边的边权。
如果想要维护整棵树的信息，我们就需要在加入一条边的时候，将端点所属的连通块，而不是端点本身，同时接到一个点权为当前边权的父节点上。重复这个过程，我们就可以得到一棵新的树，它叫做“Kruskal重构树”。在这棵树上，两个叶子节点的(LCA)就是两点之间最小边权的最大值。
Kruskal重构树有些奇妙的性质。由于构造的顺序特殊，这棵树是一个标准的二叉堆。
回看这道题。我们先以海拔为边权，构造出重构树。在重构树上，如果一个点的点权(w(x)>p)（当前水位线），那么以(x)为根的子树内，任意两点都可以开车来往。这是因为对子树内任意两点的(LCA)一定还是在子树内，而根据二叉堆性质，(w(LCA)>p)显然成立。我们先找到满足(w(x)>p)且(w( ext{father}(x)) leq p)（其中初始化(w( ext{叶子})=+infty,w(0)=0),诸如此类），则子树内叶子节点到(1)的最短路径就是答案。可以用树上倍增来找到这个点。
综上，我们总结一下算法的全过程：
- 准备三套储存边的结构体，分别储存路径，海拔和树边。
- 用Dijkstra预处理出各点到首都(1)的最短路径
dis[i] - 从大到小排序海拔边，构造出Kruskal重构树。
- 用DFS处理出以各个点为子树，子树内叶子节点到首都(1)的最短路径
subtreeDis[i],同时倍增处理出每个点的(2^k)辈祖先F[i][k] - 每次询问从出发点
u开始，倍增地找到最后一个满足w[x]>p的祖先x。subtreeDis[x]即为所求。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
#define rg register
#define fre(z) freopen(z".in", "r", stdin), freopen(z".out", "w", stdout)
#define customize template<class type> inline
typedef long long number;
const number INF = 0x3f3f3f3f3f3f3f3f;
customize type read(type sample)
{
type ret = 0, sign = 1; char ch = getchar();
while(! isdigit(ch))
sign = ch == '-' ? -1 : 1, ch = getchar();
while(isdigit(ch))
ret = ret * 10 + ch - '0', ch = getchar();
return sign == -1 ? -ret : ret;
}
const int MAXN = 400010;
const int MAXM = 800010;
customize void checkMin(type &var, type value)
{
var = value < var ? value : var;
}
int N, M;
int father[MAXN << 1];
int head[MAXN];
struct Edge{
int next;
int front, to;
number val;
}edge[MAXM]; int tot = 0;
inline void append(int front, int to, number val)
{
++ tot;
edge[tot] = (Edge){head[front], front, to, val};
head[front] = tot;
}
inline void connect(int front, int to, number val)
{
append(front, to, val);
append(to, front, val);
}
number dis[MAXN << 1];
bool used[MAXN];
priority_queue< pair<number, int> > heap;
inline void initDis()
{
memset(dis, 0x3f, sizeof(dis));
memset(used, false, sizeof(used));
while(! heap.empty())
heap.pop();
dis[1] = 0;
heap.push(make_pair(0, 1));
while(! heap.empty())
{
int cur = heap.top().second; heap.pop();
if(used[cur])
continue;
used[cur] = true;
for(rg int e = head[cur]; e; e = edge[e].next)
{
int to = edge[e].to;
if(dis[to] > dis[cur] + edge[e].val)
{
dis[to] = dis[cur] + edge[e].val;
heap.push(make_pair(-dis[to], to));
}
}
}
}
struct SimpleEdge{
int front, to;
number val;
}level[MAXM << 1];
int totLevel;
int headLevel[MAXN << 1];
Edge tree[MAXN << 1];
int next[MAXN << 1];
int nodeSize = 0, treeSize = 0;
number weight[MAXN << 1];
inline int getNext(int cur)
{
if(next[cur] == cur)
return cur;
return next[cur] = getNext(next[cur]);
}
inline void init()
{
for(rg int i = 1; i <= (N << 1); ++ i)
next[i] = i;
}
bool cmpByVal(SimpleEdge a, SimpleEdge b)
{
return a.val > b.val;
}
inline void appendTree(int front, int to)
{
++ treeSize;
tree[treeSize] = (Edge){headLevel[front], front, to, 0};
headLevel[front] = treeSize;
}
inline void attach(int front, int to)
{
appendTree(front, to);
appendTree(to, front);
}
inline void KruskalReconstruct()
{
memset(weight, 0, sizeof(weight));
sort(level + 1, level + totLevel + 1, cmpByVal);
nodeSize = N;
treeSize = 0;
for(rg int i = 1; i <= totLevel; ++ i)
{
int topNodeLt = getNext(level[i].front);
int topNodeRt = getNext(level[i].to);
if(topNodeLt != topNodeRt)
{
attach(++ nodeSize, topNodeLt);
attach(nodeSize, topNodeRt);
next[topNodeLt] = next[topNodeRt] = nodeSize;
weight[nodeSize] = level[i].val;
weight[level[i].front] = weight[level[i].to] = INF;
}
}
}
number subtreeDis[MAXN];
int multiFather[MAXN << 1][25];
inline void initSubtreeParameter(int cur, int father)//start from nodeSize
{
subtreeDis[cur] = dis[cur];
multiFather[cur][0] = father;
for(rg int k = 1; k <= 20; ++ k)
multiFather[cur][k] = multiFather[multiFather[cur][k - 1]][k - 1];
for(rg int e = headLevel[cur]; e; e = tree[e].next)
{
int to = tree[e].to;
if(to == father)
continue;
initSubtreeParameter(to, cur);
checkMin(subtreeDis[cur], subtreeDis[to]);
}
}
inline number getQuery(int u, int curLevel)
{
int subtreeRoot = u;
for(rg int k = 20; k >= 0; -- k)
{
if(weight[multiFather[subtreeRoot][k]] > curLevel)
subtreeRoot = multiFather[subtreeRoot][k];
}
return subtreeDis[subtreeRoot];
}
int main()
{
//fre("P4768");
int T = read(1);
while(T --)
{
memset(head, 0, sizeof(head));
memset(headLevel, 0, sizeof(headLevel));
N = read(1); M = read(1);
tot = 0; totLevel = 0;
nodeSize = 0; treeSize = 0;
for(rg int i = 1; i <= M; ++ i)
{
int u = read(1), v = read(1);
number l = read(1ll), a = read(1ll);
connect(u, v, l);
++ totLevel;
level[totLevel].front = u;
level[totLevel].to = v;
level[totLevel].val = a;
}
int Q = read(1), K = read(1);
number S = read(1), ans = 0;
initDis();
init();
KruskalReconstruct();
initSubtreeParameter(nodeSize, 0);
for(rg int i = 1; i <= Q; ++ i)
{
int u = read(1);
number p = read(1ll);
u = (u + K * ans - 1) % N + 1;
p = (p + K * ans) % (S + 1);
ans = getQuery(u, p);
printf("%lld
", ans);
}
}
return 0;
}