HDU3038(How Many Answers Are Wro

链接：https://vjudge.net/problem/HDU-3038
思路：带权并查集，首先我们要考虑在什么情况下会出错，当且仅当某个区间开头和位置以及和都确定并且产生矛盾的时候，于是我们建立一个带权并查集，每个区间查询其左端点-1的节点(因为左端点也要算在和内)与右端点的节点的祖先节点，如果相同说明通过其他的操作已经可以推算出这个区间的值了(自行思考推理一下)，只需要比对一下前后到祖先节点距离的差值是否等于给定的值即可，如果不等则说明没法推断出，则不会产生矛盾，此时将两个端点合并，并且更新各节点到祖先节点的距离。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 200010;
int par[maxn];
int n,m;
int sum[maxn];

int getroot(int a){
    if(par[a]==a)return a;
    int p = par[a];
    par[a] = getroot(par[a]);
    sum[a]+=sum[p];//更新到祖先节点的距离
    return par[a];
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        int res = 0;
        for(int i=0;i<=n;i++){
            par[i] = i;
            sum[i] = 0;
        }
        for(int i=0;i<m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            u--;
            int p1 = getroot(u);
            int p2 = getroot(v);
            if(p1==p2){
                if(sum[v]-sum[u]!=w)res++;//更新答案
            }
            else{
                par[p2] = p1;
                sum[p2] = sum[u] - sum[v] + w;//自行画图即可得出该表达式
            }
        }
        printf("%d\n",res);
    }
    return 0;
}