这个题看了2天！！！最后看到这篇题解才有所明悟

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4298091.html   ---by 墨染之樱花

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3038

题目描述：某个无聊的骚年给他的女友（烧！）一系列三元组x,y,c，表示序列中a_x+a_x+1+...+a_y=c。但是其中有一些是错误的，也就是与前面的信息出现了冲突，比如给了1,2,6和3,4,5接着却给了1,4,100。找出所有错误的三元组的数量

思路：正如一般带权并查集的方法。用par[i]记录父节点，d[i]记录与父节点的差值，如果x与y在不同的集合中则可以*合并，如果在同一集合中那就有可能出现矛盾。判断d[y]-d[x]==c是否成立，成立的话自然只需无视，不成立的话就表明出现矛盾。注意Find路径压缩查找当中节点到根结点路径上的每一个点除了par要修改，d也要累计。另外，由于题中给的区间都是全闭的，会出现x=y的情况，为了方便起见，记录区间时变为左闭右开，即y++

因为路径压缩后d[i] 一般就是祖先节点的值啦！。。然后直接累加到顶点 也满足路径压缩！十分棒的题目！

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

using namespace std;

const int MAXN=200010;

int F[MAXN];

int val[MAXN];

int find(int x)

{

    if(F[x]==-1)return x;

    int tmp=find(F[x]);

    val[x]+=val[F[x]];      //路径上所有点增加父亲节点的值..

    return F[x]=tmp;

}

void init()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

}

int main()

{

  //  init();

    int n,m;

    int u,v,w;

    while(scanf("%d%d",&n,&m)==2)

    {

        memset(F,-1,sizeof(F));

        memset(val,0,sizeof(val));

        int ans=0;

        while(m--)

        {

            scanf("%d%d%d",&u,&v,&w);

            u=u-1;

            int t1=find(u);

            int t2=find(v);

            if(t1!=t2)

            {

                F[t2]=t1;

                val[t2]=val[u]-val[v]+w;

            }

            else

            {

                if(val[v]-val[u]!=w)ans++;

            }

        }

        printf("%d\n",ans);

    }

    return 0;

}