526互联

【题解】P4768 [NOI2018] 归程 / Kruskal 重构树

发布时间 2023-11-13 23:25:10作者: kymru

补补以前懒得总结的零碎东西。

kruskal 重构树

使用条件：求无向图中两点之间所有路径的最大边权的最小值

构造：

  1. 依 kruskal 得到最小生成树

  2. 从小到大考虑生成树中的边 \((u, v)\)

  3. 对于 \((u, v)\)，新建一个结点，作为重构树中 \(u, v\) 的父结点

  4. 该结点的点权为 \((u, v)\) 的边权

性质：

  1. 原图中两点之间所有路径的最大边权的最小值

    = 最小生成树上两点之间路径的边权最大值

    = 重构树两点 lca 的点权

  2. kruskal 重构树是一棵二叉树

  3. kruskal 重构树以最小生成树构造时为大根堆，反之同理

  4. 令 \(v\) 该结点为重构树上 \(u\) 深度最浅的点权不超过 \(w\) 的祖先结点，则原图中结点 \(u\) 经过边权不超过 \(w\) 的边能到达的结点为 \(v\) 的子树

求最小边权的最大值同理。

思路

Kruskal 重构树。

首先意识到只经过海拔不超过定值的点可以通过 Kruskal 重构树的子树表示，答案即为子树中任意一个结点到 \(1\) 号结点经过的积水边总长的最小值。

发现其实等价于子树中结点到 \(1\) 号结点的最短路，原因考虑答案路径上最后一个非积水边的终点在所求子树内。

求子树的根结点可以考虑树上倍增。

单次时间复杂度 \(O(n \log n)\).

代码

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define il inline

const int maxn = 2e5 + 5;
const int maxm = 4e5 + 5;
const int maxt = maxn << 1;
const int lg_sz = 21;

struct edg
{
	int u, v, l, a;
	
	bool operator < (const edg& rhs) const { return (a > rhs.a); }
} edge[maxm];

int T, n, m, q, k, s;
bool vis[maxn];
int dis[maxn];
vector<int> g[maxn], w[maxn];

namespace DSU
{
	int fa[maxt];
	
	void dsu_init(int n) { for (int i = 1; i <= n; i++) fa[i] = i; }
	
	int get(int x) { return (fa[x] == x ? x : (fa[x] = get(fa[x]))); }
}
using namespace DSU;

namespace tree
{
	int nd = 0;
	int anc[maxt][lg_sz], val[maxt];
	int dp[maxt];
	vector<int> tr[maxt];
	
	void dfs(int u)
	{
		dp[u] = (u <= n ? dis[u] : 1061109567);
		for (int v : tr[u]) dfs(v), dp[u] = min(dp[u], dp[v]), anc[v][0] = u;
	}
	
	void calc()
	{
		dfs(nd);
		for (int j = 1; (1 << j) <= nd; j++)
			for (int i = 1; i <= nd; i++)
				anc[i][j] = anc[anc[i][j - 1]][j - 1];
	}
	
	int query(int u, int lim)
	{
		for (int i = lg_sz - 1; i >= 0; i--)
			if (anc[u][i] && (val[anc[u][i]] > lim)) u = anc[u][i];
		return dp[u];
	}
}
using namespace tree;

void init()
{
	for (int i = 1; i <= nd; i++) tr[i].clear();
	for (int i = 1; i <= n; i++) g[i].clear(), w[i].clear();
}

void dijkstra()
{
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
	memset(vis, false, (n + 1) * sizeof(bool));
	memset(dis, 0x3f, (n + 1) * sizeof(int)); dis[1] = 0;
	pq.push(make_pair(0, 1));
	while (!pq.empty())
	{
		int u = pq.top().second; pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = 0, v, len; i < g[u].size(); i++)
		{
			v = g[u][i], len = w[u][i];
			if (dis[v] > dis[u] + len)
			{
				dis[v] = dis[u] + len;
				pq.push(make_pair(dis[v], v));
			}
		}
	}
}

void kruskal()
{
	sort(edge + 1, edge + m + 1);
	dsu_init(n), nd = n;
	for (int i = 1; i <= m; i++)
	{
		int fu = get(edge[i].u), fv = get(edge[i].v);
		if (fu != fv)
		{
			nd++, fa[nd] = fa[fu] = fa[fv] = nd, val[nd] = edge[i].a;
			tr[nd].push_back(fu), tr[nd].push_back(fv);
		}
	}
}

void solve()
{
	scanf("%d%d", &n, &m);
	init();
	for (int i = 1, u, v, l, a; i <= m; i++)
	{
		scanf("%d%d%d%d", &u, &v, &l, &a);
		edge[i] = (edg){u, v, l, a};
		g[u].push_back(v), w[u].push_back(l);
		g[v].push_back(u), w[v].push_back(l);
	}
	dijkstra(), kruskal(), calc();
	scanf("%d%d%d", &q, &k, &s);
	int last_ans = 0;
	while (q--)
	{
		int v, p;
		scanf("%d%d", &v, &p);
		v = (v + k * last_ans - 1) % n + 1;
		p = (p + k * last_ans) % (s + 1);
		printf("%d\n", last_ans = query(v, p));
	}
}

int main()
{
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}