题意：
有兩個人在玩遊戲，有N個數，FF會詢問TT,sum(a, b)=A[a] + ... +A[b]是多少，TT會告訴他正確的答案，也會告訴他錯誤的。要你統計錯誤的答案有多少組。（如果當前的是錯的統計完就直接忽略掉）
总结：这道题花了我很长时间，结果还是看了别人的题解才想到的。其实就是一个小细节，把左区间边界-1。
思路：这题可以用大的值做父节点，也可以用小的值做父节点， 因为合并的值只是表示数组下标罢了。这里我用较小的值做父节点。设父节点是root， 当前节点是node，则sum[node]记录的是node到root这 root-node+1个元素的和。然后在同一颗树里求某一段和，假设求sum(a, b)，则 等价于sum[b]-sum[a-1]，因而这也可以用作我们的判断是否有误的依据。
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 using namespace std; 5 #define maxn 200005 6 //#define llint long long 7 int fa[maxn]; int sum[maxn]; 8 int n, m, ans; 9 void init() 10 { 11 ans = 0; 12 for(int i = 0; i <= n; i++){ 13 fa[i] = i; 14 sum[i] = 0; 15 } 16 } 17 int Find(int x) 18 { 19 if(fa[x] == x) { 20 return x; 21 } 22 int t = fa[x]; 23 fa[x] = Find(fa[x]); 24 sum[x] += sum[t]; 25 return fa[x]; 26 } 27 int Union(int a, int b, int s) 28 { 29 int x = Find(a); 30 int y = Find(b); 31 if(x == y&&sum[b]-sum[a] != s) return 1; 32 if(x > y) { 33 fa[x] = y; 34 sum[x] = sum[b] - s - sum[a]; 35 } 36 if(x < y) { 37 fa[y] = x; 38 sum[y] = s - sum[b] + sum[a]; 39 } 40 return 0; 41 } 42 void work() 43 { 44 for(int i = 0; i < m; i++) { 45 int a, b; int s; scanf("%d%d%d", &a, &b, &s); 46 ans += Union(a-1, b, s); 47 } 48 printf("%d\n", ans); 49 } 50 int main() 51 { 52 while(scanf("%d%d", &n, &m) != EOF){ 53 init(); 54 work(); 55 } 56 return 0; 57 }
HDU-3038-How Many Answers Are Wrong - 种类并查集,布布扣,bubuko.com
HDU-3038-How Many Answers Are Wrong - 种类并查集
原文：http://www.cnblogs.com/ZiningTang/p/3916312.html
