《论我自行发明了带权并查集》

题意

定义一个三元组的集合$S$，如果加入某一个三元组$(a,b,c)$之后存在一个数组$A$，使得其中每一个元素$(x,y,z)$都有$A_x-A_y=z$，就将$(a,b,c)$加入集合。

思路

考虑建一个图，图的边权就是每两个元素的差，只要其中每一个环的权值为$0$就是一个好的集合。不难发现每一次加入元素之后可能会有两个元素的$x$或$y$是相同的，这就构成了一个连通块，如果构成环就数一下他的边权即可。

但这会超时啊。

其实不难发现判断是否是好集合只需要开一个并查集即可。我的代码中的$d_i$表示在图中$i$到他的父亲节点的路径长度，如果一个元素的两端有同一个父亲，且他们的长度差不为$d$，就是不合法的。否则就将两个并查集合并（或是什么也不做）

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int fa[N],d[N],n,q;
int find(int x)
{
	if(fa[x]==x)return x;
	int xfa=find(fa[x]);
	d[x]+=d[fa[x]];fa[x]=xfa;
	return fa[x];
}
signed main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++)fa[i]=i;
	vector<int>ans;
	for(int i=1,x,y,z;i<=q;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		int tx=find(x),ty=find(y);
		if(tx==ty)
		{
			if(d[x]-d[y]==z)ans.push_back(i);
		}
		else
		{
			ans.push_back(i);
			fa[tx]=ty;
			d[tx]=d[y]+z-d[x];
		}
	}
	for(int i:ans)printf("%lld ",i);
	return 0;
}