hdu 3038How Many Answers Are Wrong 这辈子都学不会的带权并查集(略懂篇章)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3038

题意：就给你n个数，然后给你m次区间和的信息，问你有多少个是错的。

思路：出现错的情况只有是大区间包括小区间，而且小区间的值大于大区间（因为不存在负值），就用到了带权并查集，将区间不断连接在一起。

用到了位偏移的知识点：（资料借鉴：https://www.cnblogs.com/liyinggang/p/5327055.html）

 

这题我们利用一个valu[]数组保存从某点到其祖先节点距离。

1.从上图我们可以看出，当roota != rootb时 如果将roota并入rootb，那么是不是 roota->rootb = b->rootb  -  b->roota

然后我们可以知道 b->roota = a->roota - a->b

所以最后可以推出 roota ->rootb = b->rootb + a->b - a->roota

而roota的根节点是rootb,所以 roota->rootb = sum[roota]

然后依次推出得到 sum[roota] = -sum[a]+sum[b]+v （这里的a要说明一下由于是区间 [a,b] ，[a,b] = [root,b]-[root,a-1],所以a要减一）

2.如果roota==rootb 是不是 a和b的根节点已经相同了？所以我们只要验证 a->b是否与题中的长度一致了。

所以 a->b = a->root - b->root

然后得到表达式 v = sum[a]-sum[b] (一定要记住这里的sum都是相对于根节点的，sum的更新在路径压缩的时候更新了)

说明：代码中变量与上不一，上只是思想。

网站并没有提醒是多组，但是不加多组就WA，加了就AC了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200010;
int fa[maxn];
int valu[maxn];
int find(int x)
{
	if(fa[x]==x)
		return x;
	int fx=fa[x];
	fa[x]=find(fa[x]);
	valu[x]=valu[x]+valu[fx]; //求和 
	return fa[x];
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)
	{
		fa[i]=i;
		valu[i]=0;
	}
	int ans=0;
	for(int i=0;i<m;i++)
	{
		int u,v,Valu;
		scanf("%d%d%d",&u,&v,&Valu);
		u--;
		int fx=find(u);
		int fy=find(v);
		if(fx==fy)//同一个区间 
		{
			if(valu[u]-valu[v]!=Valu)
				ans++;
		}
		else//不同区间 
		{
			fa[fx]=fy;
			valu[fx]=-valu[u]+valu[v]+Valu;	
		} 
	}
	printf("%d\n",ans); 
	return 0;
}