题目链接：
POJ 3038 How Many Answers Are Wrong
题意：
n表示n个数字，编号1–n，然后有m个区间[l,r]和该区间和s，
问在这m个区间中有多少个区间和是不正确的？
如果不正确就忽略该区间和，否则将该区间和作为已知条件使用。
分析：
需要一个数组val,val[i]表示i到根节点的距离，然后就是在查找根节点的过程更新路径上结点的val,和在mix函数里判断该区间和是否有效。
l到r之间的和为s可以理解为l-1到r的距离为s。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
using namespace std;const int maxn = 200010;int val[maxn], pre[maxn];//val[i]:i到根节点的距离；pre[i]：i的父节点
int n, m, u, v, w;int find(int x)//递归寻找x的根节点
{if (pre[x] == x) return x;int tmp = find(pre[x]);//tmp是x的根节点val[x] = val[x] + val[pre[x]];//在递归时x还未连接到根节点上，只连接到父节点上，所以这时的val[x]实际上是到父节点的距离//而val[pre[x]]是父节点到根节点的距离，所以真正的val[x]=val[x]+val[pre[x]]，左边的val[x]是到根节点距离，右边的是到父节点距离//可以从递归倒数第二层往前想return pre[x] = tmp;//路径压缩
}int mix(int x, int y, int z)
{int fx = find(x);int fy = find(y);if (fx != fy){pre[fx] = fy;//将x的根节点fx的父节点设为fyval[fx] = val[y] - val[x] + z;//x到y的距离是z，x到fx的距离是val[x]，y到fy的距离是val[y],//那么fx到fy的距离val[fx]=x到fy的距离（z+val[y]）- x到fx的距离（val[x]）return 0;}else{if (abs(val[y] - val[x]) == z) return 0;//必须是绝对值才行//因为尽管y>x，但是到根节点的距离不确定大小（到根结点路径上个点的值大小不确定）return 1;}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endifwhile (~scanf("%d%d", &n, &m)){for (int i = 0; i <= n; i++)//因为接下来由u--的存在，所以要从0开始pre[i] = i;memset(val, 0, sizeof(val));int ans = 0;for (int i = 1; i <= m; i++){scanf("%d%d%d", &u, &v, &w);u--;//这样做符合val的含义ans += mix(u, v, w);}printf("%d\n", ans);}return 0;
}