题意：n个数，m次询问，每次问区间a到b之间的和为s，问有几次冲突

思路：带权并查集的应用。[a, b]和为s，所以a-1与b就能够确定一次关系。通过计算与根的距离能够推断出询问的正确性

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int MAXN = 200010;

int f[MAXN],arr[MAXN];

int m,n;

int find(int x) {

	if (f[x] == x)

		return x;

	int tmp = find(f[x]);

	arr[x] += arr[f[x]];

	return f[x] = tmp;

}

int main() {

	while (scanf("%d%d", &n, &m) != EOF) {

		for (int i = 0; i <= n; i++)

			f[i] = i;

		memset(arr, 0, sizeof(arr));

		int ans = 0;

		for (int t = 0; t < m; t++) {

			int a,b,s;

			scanf("%d%d%d", &a, &b, &s);

			a--;

			int f1 = find(a);

			int f2 = find(b);

			if (f1 != f2) {

				f[f2] = f1;

				arr[f2] = arr[a]+s-arr[b];

			}

			else if (arr[b]-arr[a] != s)

				ans++;

		}

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

	}

	return 0;

}