Sol.CF1633E

前言

题目内容不多赘述。

反正，我管这东西，叫“绝对值函数最小生成树”。

这道题想出解法的核心就在于他给的数据范围（其实有提示的作用），还有绝对值函数的性质。

话不多说，我们开始正题。

分析

由题目中几个关键的数据范围：

\(1 \leq n \leq 50\)

\(n-1 \leq m \leq 300\)

\(p \leq k \leq 10^7\)

以及做一次最小生成树（MST）的时间复杂度是 \(mlog(m)\)（kruskal 算法），我们大概可以把对 \(k\) 次询问每一个询问做一次 MST 的 BF 想法推翻，那么现在该怎么做呢？

不妨来观察一下题目条件中所给的绝对值函数的性质。

我们画个图（使用 geogebra）：

我们知道，在这道题里面，做 MST 时每条边的权值应该是给定 \(q\) （或者说 \(x\)）以后的权值（对应到图中便是给定横坐标 \(x\)，每个函数（边权值）所对应的 \(y\) 值）。

然后看图可以发现，在一定范围内，边权函数的大小关系是确定的，然后增减性也是确定的，考虑 kruskal 算法的排序过程，不难发现当函数大小关系确定时，求出的 MST 也是唯一的。

好了，所以现在我们按照这些绝对值函数彼此之间还有它们与 \(x\) 轴的交点，将数轴分段，对于每一段求出它开始点 \(x\) 值对应的答案，并且统计增减性。这样，对于每一个 \(q\) 我们可以二分查找到它的所在段，然后根据增减性 \(O(1)\) 地计算出答案。

由以上过程可知，该算法总复杂度为： \(O(m^3log(m)+klog(m^2))\)，可以通过本题。

要注意的细节：

1. kruskal 排序边权时，以加绝对值后的边权为第一关键字升序，以加绝对值前的边权为第二关键字降序排序，这样可以让每一段中的减函数尽可能多，保持答案最小的正确性。

2. 不开 long long 见祖宗。

3. 分段端点要去重。

参考代码（有点丑）：

/*
  Author:Lucky_Yukikaze
  
*/
#include
#define int long long
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define re register
#define pb push_back
#define mp make_pair
#define pf pop_front
#define pob pop_back
#define fr front
#define bk back

using namespace std;
typedef pair pii;
typedef long double ld;
typedef pair pll;

int n,m;

struct dsu{
	
	int fa[55];
	
	void init(int x){
		for(int i=1;i<=x;i++)fa[i]=i;
	}
	
	int getfa(int x){
		return (fa[x]==x)?(x):(fa[x]=getfa(fa[x]));
	}
	
	bool merge(int x,int y){
		int fx=getfa(x),fy=getfa(y);
		if(fx==fy)return false;
		else{
			fa[fx]=fy;
			return true;
		}
	}
	
}bcj;

struct edge{
	int u,v,w,ow;
}e[310],et[310];

struct point{
	int val,up;
}poi[90010],uni[90010];int tot=0,cnt=1;
int ans[90010];

int bins(int q){
	int l=1,r=cnt;
	int res;
	while(l<=r){
		int mid=(l+r)>>1;
		if(uni[mid].val<=q)res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);

	cin>>n>>m;
	
	
	for(int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+1+m,[](edge tp1,edge tp2){return tp1.wtp2.ow):(tp1.w>p>>k>>a>>b>>c;
	
	int final=0;
	int q;
	for(int i=1;i<=p;i++){
		cin>>q;
		int pos=bins(q);
		int tp=((ans[pos])+(q-uni[pos].val)*uni[pos].up-(q-uni[pos].val)*(n-1-uni[pos].up));
		final^=tp;
	}
	
	for(int i=p+1;i<=k;i++){
		q=(q*a+b)%c;
		int pos=bins(q);
		int tp=((ans[pos])+(q-uni[pos].val)*uni[pos].up-(q-uni[pos].val)*(n-1-uni[pos].up));
		final^=tp;	
		}
	
	cout<