【题解】P4768 [NOI2018] 归程（树上倍增，Kruskal 重构树，dijkstra）

【题解】P4768 [NOI2018] 归程

作为一道 NOI 的 D1T1放在现在或许难度不够()但可能在 Kruskal 重构树还未普及的当时还是相对来说比较难的一道题吧。

写篇题解记录一下。

---

题目链接

P4768 [NOI2018] 归程

题意概述

给定一张 \(n\) 个点 \(m\) 条边的无向图对于每条边有两个参数长度 \(l\) 和海拔 \(a\)。

有 \(Q\) 组询问每组询问给定 \(v,p\)表示每一天以 \(v\) 作为起点\(1\) 作为终点问从走到的第一条海拔 \(\le p\) 的边开始在它及它之后走到的所有边的边权之和最小是多少。

本题多测。

思路分析

考虑将每一天的所有路程分为两部分先从 \(v\) 走到最后一条海拔 \(> p\) 的边 \(u\)再从 \(u\) 走到 \(1\)。

题目要求的就是从 \(u\) 到 \(1\) 的边权之和最小是多少。

我们首先思考这里的 \(u\) 需要满足什么条件。

有以下两点

• \(v\) 不经过海拔 \(\le p\) 的边能够到达 \(u\)
• \(u\) 到 \(1\) 的边权和最小。

对于第一点可以发现它其实是一个比较板的 Kruskal 重构树的模型。

由于是“不经过海拔 \(\le p\) 的边”那么实际上就相当于“经过的边只有海拔 \(>p\) 的”。

以海拔为边权建图问题就转化为从 \(v\) 开始只经过边权 \(>p\) 的边能够到达哪些点。

显然我们可以直接将边权从大到小排序然后建立 Kruskal 重构树。

若不考虑边权 \(>p\) 的限制那么对于一个点 \(u\) 能够到达的点就是和它在一个联通块内的所有点。

再考虑边权的限制根据 Kruskal 的性质从叶子节点到根节点一路往上走点权一定是递减的。

那么根据这个性质从一个点 \(u\) 出发能够到达的边权 \(>p\) 的点一定是从 \(u\) 到根节点的路径上的某个点 \(x\) 的子树内所有的点。且这个 \(x\) 的点权一定是从 \(u\) 走到根节点的路径上最后一个点权 \(>p\) 的。

换句话说假如从 \(u\) 到根节点的路径上\(x\) 的点权 \(>p\)且 \(x\) 之后点的点权都 \(\le p\)那么 \(x\) 的子树内的所有点就是符合题意的点。

这一点很容易证明

• 首先证明 \(x\) 子树内的所有点一定满足题意。这个根据 Kruskal 的性质即若 \(x\) 的子树中存在两点 \(u,v\)那么实际的图上 \(u\) 到 \(v\) 的路径上最小边权的最大值一定等于 \(x\) 的点权。所以 \(x\) 的点权是其子树中任意两点的路径上的最小边权最大值那么既然最小边权都 \(>p\) 了那么其它的也一定 \(>p\)所以满足题意
• 再证明从 \(u\) 到根节点的路径上的其它点都不满足题意。
  • 对于 \(x\) 之前的点显然 \(x\) 的子树完全包含它之前的点那么显然将答案设在 \(x\) 之前的点会漏掉一些点所以不优。
  • 对于 \(x\) 之后的点由于其点权一定 \(\le p\)那么其子树内的任意两点的最小边权最大值一定 \(\le p\)不符合要求边权 \(>p\) 的限制所以只有 \(x\) 子树内的点满足条件。

那么证明了答案在 \(x\)那么怎么找到 \(x\) 呢。其实可以直接树上倍增。

预处理出来一个数组 \(fa_{x,i}\) 表示从 \(x\) 向上走 \(2^i\) 步能够到哪。然后我们往上倍增的跳假设当前在 \(now\)只要 \(fa_{now,i}\) 的点权 \(>p\) 就跳反之不跳。即可找到满足条件的 \(x\)。

我们找到了 \(x\)相当于只完成了第一点。

即符合第一个条件的点一定在 \(x\) 的子树内。考虑第二点满足条件的 \(u\) 就是 \(x\) 子树内到 \(1\) 的最短路最小的点。

从一个点到 \(1\) 的最短路可以直接建立反图 dijkstra 求出。

而如何判断 \(x\) 子树内哪个点距离 \(1\) 最近呢

直接暴力枚举吗显然时间复杂度炸了。

实际上我们可以直接处理出来一个数组 \(mi_{now}\) 表示 \(now\) 所在子树内距离 \(1\) 最近的点的距离是多少。

由于重构树是个二叉树那么可以直接用类似线段树 pushup 的操作求即 \(mi_{now}=\min\{mi_{now},mi_{ls},mi_{rs}\}\)。

总复杂度 \(O(T n\log n)\)。

易错点

• 注意多测清空
• 注意有些数组要开二倍空间
• 注意重构树的边比原树多了 \(n-1\) 条
• 注意强制在线 \(lastans\) 变量的更新

代码实现

//luoguP4768
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#define int long long
using namespace std;
const int maxn=2e5+10;
int fa[maxn<<1],vis[maxn<<1],dis[maxn],sum[maxn<<1],val[maxn<<1];
int mi[maxn<<1][25],f[maxn<<1][25],dep[maxn<<1];
int n,m,tot;

struct nod{int u,v,w;}e[maxn<<1];

struct Node{
	int v,w;
	bool operator<(const Node &t)const
	{
		return w>t.w;
	}
};

basic_string<Node>edge[maxn];
basic_string<int>edge2[maxn<<1];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int cmp(nod a,nod b){return a.w>b.w;}

int find(int x)
{
	if(x!=fa[x])fa[x]=find(fa[x]);
	return fa[x];
}

void add(int x,int y)
{
	x=find(x);y=find(y);
	fa[x]=y;
}

void dfs(int now)
{
	for(int nxt:edge2[now])
	{
		dfs(nxt);
		sum[now]=min(sum[now],sum[nxt]);
	}
}

void Kruskal()
{
	for(int i=1;i<=(n<<1);i++)fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(find(e[i].u)==find(e[i].v))continue;
		int x=find(e[i].u),y=find(e[i].v);
		add(e[i].u,e[i].v);
		val[++tot]=e[i].w;
		fa[x]=fa[y]=fa[tot]=tot;
		edge2[tot]+=x;edge2[tot]+=y;
	}
}

void dijkstra(int s)
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)dis[i]=(1ll<<60);
	dis[s]=0;
	priority_queue<Node>q;
	q.push(Node{s,dis[s]});
	while(!q.empty())
	{
		Node now=q.top();
		q.pop();
		if(vis[now.v])continue;
		vis[now.v]++;
		for(Node y:edge[now.v])
		{
			if(dis[y.v]>dis[now.v]+y.w)
			{
				dis[y.v]=dis[now.v]+y.w;
				q.push(Node{y.v,dis[y.v]});
			}
		}
	}
	for(int i=1;i<=n;i++)sum[i]=dis[i];
}

void dfs2(int x,int fath)
{
	dep[x]=dep[fath]+1;
	mi[x][0]=val[fa[x]];
	f[x][0]=fath;
	for(int i=1;i<=20;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		mi[x][i]=min(mi[x][i],mi[f[x][i-1]][i-1]);
	}
	for(int y:edge2[x])
	{
		if(y==fath)continue;
		dfs2(y,x);
	}
}

signed main()
{
	int T=read();
	while(T--)
	{
		for(int i=1;i<=n;i++)edge[i].clear();
		for(int i=1;i<=(n<<1);i++)edge2[i].clear();
		memset(dep,0,sizeof(dep));
		n=read();m=read();
		for(int i=1;i<=m;i++)
		{
			int u,v,l,a;
			u=read();v=read();l=read();a=read();
			e[i]=nod{u,v,a};
			edge[u]+=Node{v,l};
			edge[v]+=Node{u,l};
		}
		dijkstra(1);
		tot=n;
		Kruskal();
		for(int i=n+1;i<=(n<<1);i++)sum[i]=(1ll<<60);
		dfs(tot);
		dfs2(tot,0);
		int q=read(),k=read(),s=read();
		int lastans=0;
		while(q--)
		{
			int v0=read(),p0=read();
			int v=(v0+k*lastans-1)%n+1;
			int p=(p0+k*lastans)%(s+1);
			int now=v;
			for(int i=20;i>=0;i--)
			{
				int cha=dep[now]-dep[tot];
				if((cha>=(1<<i))&&val[f[now][i]]>p)
				{
					now=f[now][i];
				}
			}
			cout<<sum[now]<<'\n';
			lastans=sum[now];
		}
	}
	return 0;
}