带权并查集

题目链接：https://cn.vjudge.net/problem/HDU-3038

具体大意：给你多次询问，每一次输入三个值，前两个代表区间，最后一个代表这个区间的值。问你这多次询问中有几次时候矛盾的。

举个例题 

  1 2 3

1 2 4  ，这不就矛盾了，，，

具体思路：首先每一个点都是自己的区间，在每一次更新的过程中，这个点的父节点是当前点往前最多知道到哪个点的区间是清楚的。这样的话，每一次更新的时候，如果当前的区间已经知道了。比如说 3 4 5，那么就直接将1到4的距离减去1 2 的距离，得到的就是3 到5 的距离，然后再比较就可以了。

如果当前的区间不清楚，那么就需要更新，尽量往前更新。比如说 3 4 5,假设3的父亲节点1,  4的父亲节点是2

1 2 3 4

这样的话，就能够计算出1到2 的距离，也就是3的父亲节点和4的父亲节点的距离，然后再将4的父亲节点进行更新。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<stdio.h>
using namespace std;
# define maxn 200000+10
# define ll long long
int father[maxn];
int sum[maxn];
int n,m;
int Find(int t)
{
    int temp=father[t];
    if(t!=father[t])
    {
        father[t]=Find(father[t]);
        sum[t]+=sum[temp];
    }//更新的过程，既然父亲节点还没有对应起来，那么就是这段距离肯定还没有加上。
    return father[t];
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1; i<=n; i++)
        {
            father[i]=i;
            sum[i]=0;
        }
        int ans=0;
        while(m--)
        {
            int t1,t2,w;
            scanf("%d%d%d",&t1,&t2,&w);
            if(t1>t2)swap(t1,t2);
            t1--;
            int x=Find(t1);
            int y=Find(t2);
            if(x==y&&sum[t2]-sum[t1]!=w)ans++;
            if(x>y)
            {
                father[x]=y;
                sum[x]=sum[t2]-(w+sum[t1]);//注意，更新的是父亲节点。
            }
           if(x<y)
            {
                father[y]=x;
                sum[y]=sum[t1]+w-sum[t2];
            }
        }
        printf("%d
",ans);
    }
    return 0;
}