HDU-3038 How Many Answers Are Wrong （带权并查集）

题意：给出区间[1,n]，m个条件：[u,v]的和为w，求有几条与前面的条件矛盾

数据范围：1 <= n <= 2e5，m <= 40000

终于看懂了啊。。。之前一直没弄懂，问了大佬也没问明白我觉得这题目纠结和别扭的点。

推荐一篇博客：https://www.cnblogs.com/liyinggang/p/5327055.html

之前我看不懂的时候也在看这篇，现在看懂也是在这篇，解释得真的很棒，感谢作者

就我自己卡住的点解释一下：这题给的是区间，我没想明白怎么处理这个区间矛盾关系，专题又告诉我这是并查集，于是被带入了“把区间放进并查集？？？”的误区，虽然我自己也觉得这样的脑洞不靠谱。。。实际上先不看w这个值，像我们最开始学习的并查集处理连接关系那样，还是把u，v两个点（或它们的根结点）（而不包括中间的）连在一起，我们需要处理的问题是：怎样通过u->root_u，v->root_v确定u->v的值，上面的博客用向量偏移的思想讲得很清楚，把并查集的边看作向量，通过向量加减法，就能求出u->v，如果u->v在不合并时就已经存在，就可以判断对错了。

再联系一下并查集的作用：快速判断两个点是否是同一集合，快速合并两个集合

#include<cstdio>
#include<algorithm>
using namespace std;

const int mx = 2e5+10;
int sum[mx], pa[mx];

int fx(int x) {
    if (x != pa[x]) {
        int t = pa[x];
        pa[x] = fx(pa[x]);
        sum[x] += sum[t];
    }
    return pa[x];
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            pa[i] = i;
            sum[i] = 0;
        }
        while (m--) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            u--;
            int a = fx(u), b = fx(v);
            if (a != b) {
                pa[a] = b;
                sum[a] = sum[v]-sum[u]+w;
            }
            else if (sum[u]-sum[v] != w) ans++;
        }
        printf("%d
", ans);
    }
    return 0;
}