题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3038
题解转载自：https://www.cnblogs.com/liyinggang/p/5327055.html
题目大意：有n个数，你不知道具体是啥，只知道有n个，然后输入m组数据，每组包含三个整数，a,b，s，表示区间[a,b]的整数和为s，输出有错误的数据的组数。
解题思路：是个典型的带权并查集，难点就在于更新相对信息值。在查找和合并也要对相对信息值进行更新。
做法是用一个数组存储某个节点到其根节点的距离。把区间的总和看成是两个端点的相对距离。
极力推荐这位大牛的博客：http://blog.csdn.net/niushuai666/article/details/6981689
这题让我学到了很多，特别是关于向量偏移，可以直接找到根节点与子节点的关系
这题我们利用一个sum[]数组保存从某点到其祖先节点距离。
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的更新在路径压缩的时候更新了)
1 #include<stdio.h>
2 #include<string.h>
3 #include<iostream>
4 using namespace std;
5 const int maxn=200005;
6 int par[maxn],rank[maxn],ans;
7
8 int find(int x)
9 {
10 if(par[x]==x)
11 return x;
12 int temp=find(par[x]);
13 rank[x]+=rank[par[x]];
14 return par[x]=temp;
15 }
16
17 void unite(int x,int y,int s)
18 {
19 int rootx=find(x);
20 int rooty=find(y);
21 if(rootx!=rooty)
22 {
23 par[rooty]=rootx;
24 rank[rooty]=rank[x]+s-rank[y]; //用向量的思维，合并后rooy到rootx的距离就等于x到根距离加上x和y的距离减去y到rooty的距离
25 }
26 else
27 {
28 if(rank[x]+s!=rank[y])
29 ans++;
30 }
31 }
32
33 signed main()
34 {
35 int n,m;
36 while(scanf("%d%d",&n,&m)!=EOF)
37 {
38 for(int i=1;i<=n;i++)
39 par[i]=i,rank[i]=0;
40 ans=0;
41 while(m--)
42 {
43 int a,b,s;
44 scanf("%d%d%d",&a,&b,&s);
45 a--;
46 unite(a,b,s);
47 }
48 printf("%d
",ans);
49 }
50 return 0;
51 }
52